确定有限自动机DFA和非确定有限自动机NFA

确定自动机DFA

定义：

两种表示方式

• 状态转换图

三种节点：终止状态，非终止状态，开始状态
边：状态转换函数
举例：

• 状态转换矩阵

概括：用二维数组的方式表示状态机
注意：右上角+号代表初始状态，右上角*号表示终止状态
举例：

陷阱状态（错误状态）

状态图表现为非终止节点，有自己指向自己的状态转换函数
状态转换矩阵表现为对应元素为空

DFA的确定性体现

1. 初始状态唯一
2. 状态转换函数为单值函数
3. 没有输入为ε，即不接受没有任何输入就进行状态转换

DFA接受字符串

对于∑中的任何字符串a1a2…an,若在DFA M中存在一条从初始结点到某一终止结点的路径，且这条路上所有弧上的标记符连接成的字符串等于a1a2…an,则称该字符串可为DFA M所接受（识别）

DFA接受的语言

定义： DFA M所能接受的字符串的全体，称为DFA M 接受(识别)的语言，记为L(M)。

DFA程序实现

• 直接转向法
• 状态矩阵实现

DFA化简

最小自动机定义：

所以自动机最小化就是两个问题，

• 一个是合并可以合并的等价状态
• 一个是删去无用的无关状态。

如果一个自动机没有这两种状态，那他就是我们所说的最简自动机，我们想要化简自动机的话只需要把这两个工作都完成就可以了。对于第二种类型来说是比较好处理的，看一个节点是否有通路其实一看就知道了，找到这类状态直接删掉。麻烦的是等价状态，哪些状态是可以合并的，哪些是不能的，有时候简单的可以看出来，但是任给你一个自动机，你想直接看出来是很难的，所以下面就要介绍怎么化简。

两个状态机等价的条件：

化简方法：

• 状态分离法
  
  举例：
  
  
  

非确定有限自动机NFA

定义

举例（状态矩阵表示）

NFA接受的语言

定义：设A是一个NFA，A= (S,∑, f, S0, Z), 则定义A接受（识别）的语言L(A)为从任意初始状态到任意终止状态所接受的字符串的集合。

程序实现

相较DFA，实现困难

与DFA的等价

定义:

设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2)，则称A1和A2等价。

定理：

对于任意一个非确定自动机A，都存在一个确定自动机A’，使得L(A)=L(A’)。

确定化

NFA确定化定义：

由NFA构造出与其等价的DFA称为NFA确定化。

确定化算法：

• 无ε空边NFA转换为DFA------NFA确定化子集法构造思想：
  
• 带ε空边NFA转换为DFA：
  引入几个定义:

状态集J的ε闭包:

状态集I经过输入a的转换状态集合

举例：

DFA和NFA的区别

正则表达式和有限自动机的相互转化

正则表达式到NFA的转换：（之后可以进行确定化，最简化）

NFA到正则表达式的转换：