确定有限自动机（DFA）

确定有限自动机(Deterministic Finite Automata，DFA) M是一个五元式  M=(S, , f, S0, F)，其中：

1.S: 有穷状态集

2.：输入字母表(有穷)

3.f: 状态转换函数，为S´SS的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’，s’称为s的一个后继状态

4.是唯一的一个初态

5.F   S ：终态集(可空)

 

PS：根据图1.1.来说

1.有穷状态集即带圈圈的数字的集合

2.字母表即从一个数字圈圈变成下一个数字圈圈的条件的集合

3.状态转换函数就那个箭头，也就是怎么转换的具体过程

4.初态就是入口

5.终态就是出口

 

eg：

DFA M=( {0，1，2，3}，{a，b}，f，0，{3})， 其中f定义如下：

f(0，a)=1  f(0，b)=2 

f(1，a)=3      f(1，b)=2

f(2，a)=1  f(2，b)=3

f(3，a)=3   f(3，b)=3

 

---

确定有限自动机产生语言

  对于中的任何字a，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于a，则称a为DFA M所识别(接收)                  PS：括号忽略掉，=的闭包

DFA M所识别的字的全体记为L(M)

 PS：这句话就是说只要存在一条从入口到出口的路。这条路上的字母组成的字符串就能被该自动机识别并处理

 eg：

 这个识别的就是所有以00结尾的串也就是说，

                      该自动机M产生的语言是         L(M)={以00结尾的串}

再举例

    以下哪个DFA能识别  {}？

  

 

很显然 ，A 能够识别一个字。因为系统初始处于初态q0，不读入任何字符也是停留在q0，而q0又是终态，所以相当于从初始状态q0出发，读入了长度为0字符串，停留在终止状态q0，也就是识别了。或者从路径上理解，q0到q0就是一个从初态到终态的通路，通路上的标记构成的字符串就是。

     再来看看图B，B 能识别任什么字？因为系统初始处于初态q0，q0没有射出弧，无法读入任何字符而转入别的状态，而q0本身也不是终态，也不存在从初态到终态的通路，连也不能识别。所以B不能识别任何字，所以，识别的字的集合是空集。

 

 

---

---

非确定有限自动机（NFA）

定义：一个非确定有限自动机(Nondeterministic Finite Automata，NFA) M是一个五元式M=(S, , f, S0, F)，其中：

1.S: 有穷状态集

2. ：输入字母表(有穷)

3.f: 状态转换函数，为S´S*的部分映射

4.是非空的初态集

5.F S ：终态集(可空)

 

 PS：与确定有限自动机不同的是，f 状态转换函数和它的初态可以有多个！

确定有限自动机的f是单值映射，也就是f的函数的转换条件只能是一个，比如说当输入字母a从状态1转换到状态2。

但是非确定有限最自动机的部分映射，即比如当输入a或者b的时候从状态1转换到状态2，即转换条件的数量

看下面eg的图可能比较容易理解

 

从状态图看NFA 和DFA的区别

• NFA可以有多个初态
• 弧上的标记可以是S*中的一个字(甚至可以是一个正规式)，而不一定是单个字符
• 同一个字可能出现在同状态射出的多条弧上
• DFA是NFA的特例 

 eg：

 

 

---

非确定有限自动机产生语言

 同确定有限自动机一样产生方式类似，只不过需要 忽略 

 

---

 

DFA和NFA

• 定义：对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与M’等价
• 自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的
• 对于每个NFA M存在一个DFA M’，使得 L(M)=L(M’)
• DFA与NFA识别能力相同，故二者可以相互转化

	NFA	DFA
初始状态	不唯一	唯一
弧上的标记	字(单字符字、)	字符
转换关系	非确定	确定

等价性证明略

 

 

---

子集法

NFA确定化--子集法

• 设I是的状态集的一个子集，定义I的-闭包-closure(I)为:
• 若s I，则se-closure(I)；
• 若sI，则从s出发经过任意条弧而能到达的任何状态s’都属于-closure(I)  即，

 -closure(I)=I   {s’ | 从某个s I出发经过任意条弧能到达s’}