！！编译原理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表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

一、转换状态不同

1、确定的有穷自动机：当一个状态面对一个输入符号的时候，所转换到的是一个唯一确定的状态。

2、不确定的有穷自动机：当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合。

二、特点不同

1、确定的有穷自动机：系统具有一系列离散的输入输出信息和有穷数目的内部状态。

2、不确定的有穷自动机：允许在每一步上读头的内部状态可在几个状态中任取，即 δ 之值为内部状态之集合。

三、映射不同

1、确定的有穷自动机：将S×Σ映射到S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。

2、不确定的有穷自动机：将S×Σ映射到2S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合。

百度百科-不确定型有穷自动机

百度百科-确定型有穷自动机

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com