有穷自动机DFA、NFA与正则文法、正规式之间都可以互相转换

文章目录

（1）有穷自动机（看看就行）1.定义：2.意义：3.分类（2）确定的有穷自动机（DFA）1.定义2.例子(重要！)2.2.状态转换图:2.3.状态转换矩阵3.DFA识别（接受字符串）①例子：（3）不确定有穷自动机（NFA）1.定义2.例子（重要！）:3.NFA识别的字符串（看一下就好了，跟前面DNF差不多道理）（4）DNA与NFA的等价性(概念重要！)（5）NFA 转 DFA(重点!!)1.方法：（子集法）4.例题3（自己再写一次，在4月12日的ppt）(4)常用的'正则式'转'状态图'（5）正则文法转自动机2.例子：（重要！！背一背！可能会忘！）

（1）有穷自动机（看看就行）

1.定义：

是一种识别装置，能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合

2.意义：

为词法分析程序的自动构造寻找特殊的方法和工具

3.分类

①确定的有穷自动机 ②不确定的有穷自动机

（2）确定的有穷自动机（DFA）

1.定义

2.例子(重要！)

2.1.题目：

2.2.状态转换图:

①有穷自动机的初态为唯一初态结点，用⇒标记 ②终态对应终态结点，用双圈表示。 ③若有f（k，a）=k，则有结点k到结点k画标记为a的弧。

2.3.状态转换矩阵

① 行表示状态，用双箭头⇒表示初态，否则第一行是初态 ②列表示输入字符 ③相应状态行和输入字符列下的新状态，即k行a列为f（k，a）的值 ④最右边的0、0、0、1，右端标0是非终态行，标1是终态行

3.DFA识别（接受字符串）

①例子：

（意思就是输入字符集能否使它从这个DFA的初态到终态）

（3）不确定有穷自动机（NFA）

1.定义

2.例子（重要！）:

3.NFA识别的字符串（看一下就好了，跟前面DNF差不多道理）

（4）DNA与NFA的等价性(概念重要！)

1.DFA是NFA的特例 2.对于任何两个有穷自动机M和N,如果L(M)=L(N)，则称M与N是等价的 3.对于每个NFA M，存在一个与其等价的DFA M ’

（5）NFA 转 DFA(重点!!)

1.方法：（子集法）

2.例题1 （可以求到 开始符集合）

3.例题2（自己再写一次） （可以求到每一步经过输入字符后到达的状态，和经过ε之后到达的状态的集合）

4.例题3（自己再写一次，在4月12日的ppt）

①包含了初态的就是初态集合 ②包含了终态的就是终态集合

(4)常用的’正则式’转’状态图’

（①②③都重要，再重点看看③！！③！！）

题目例子： （其实可以直接写最后那行的）

（5）正则文法转自动机

1.定义：（这个定义不重要，看后面例子就好了）

2.例子：（重要！！背一背！可能会忘！）

①正规文法是3型文法，特点就是右部的最左边那一个字符是终结符 ②注意看看图里的 ε 和 T