百度作业网编译原理DFA和NFA
来源：学生作业帮 编辑：百度作业网作业帮 分类：综合作业 时间：2024/07/15 01:36:20
编译原理DFA和NFA
一直不是很清楚DFA和NFA到底是做什么的,是一种算法么?比如我要做一个词法分析器,那么编写程序的过程中它们起到什么作用?麻烦举个例子说明一下,它们存在的意义是什么?纠结很久了
一直不是很清楚DFA和NFA到底是做什么的,是一种算法么?比如我要做一个词法分析器,那么编写程序的过程中它们起到什么作用?麻烦举个例子说明一下,它们存在的意义是什么?纠结很久了
DFA或NFA是对计算机程序的行为的抽象模型.你编写的程序其实就对应了一个自动机.简单举例来说,如果a,b可以取值0或1; 程序：if(a==1) b=1; 这个程序对应了一个自动机.
对应的自动机就有状态 (0,0),(0,1),(1,1),(1,0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时,运行程序的下一个状态就是(1,1).
画图出来就是 这4个状态作为顶点,并且有下面几条边
(0,0) --> (0,0)（自环）,(1,0)-->(1,1),(1,1)-->(1,1)（自环）,(0,1)-->(0,1)自环
存在的意义就是一种理论模型,也可以认为是一种编程思想.词法分析系也离不开 if else,这一系列的if else和条件也就组成自动机.
最经典体现自动机思想的算法就是KMP算法,你肯定学过,字符串子串匹配的算法.回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机!算法第二步将原串作为自动机输入,自动机的输出就是匹配到的子串位置或者无匹配.
对应的自动机就有状态 (0,0),(0,1),(1,1),(1,0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时,运行程序的下一个状态就是(1,1).
画图出来就是 这4个状态作为顶点,并且有下面几条边
(0,0) --> (0,0)（自环）,(1,0)-->(1,1),(1,1)-->(1,1)（自环）,(0,1)-->(0,1)自环
存在的意义就是一种理论模型,也可以认为是一种编程思想.词法分析系也离不开 if else,这一系列的if else和条件也就组成自动机.
最经典体现自动机思想的算法就是KMP算法,你肯定学过,字符串子串匹配的算法.回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机!算法第二步将原串作为自动机输入,自动机的输出就是匹配到的子串位置或者无匹配.