一、非确定性有限自动机 组成部分
非确定性有限自动机 : Nondeterministic Finite Automaton , NFA ;
① Q 状态集 : 有限个状态 ;
② Σ 字母表 : 有限个字符集 , 长度有限的字符串 ;
③ δ 转移函数 ( 指令集 ) : δ 称为转移函数 ; 基于当前的 自动机 的某个状态 , 将字符集 输入到自动机中 , 该自动机转换成一个或多个状态 , 这个转换就是通过 δ 转换函数进行的 , 使用公式描述
④ q0 起始状态 : 是自动机的开始状态 ;
⑤ F 接受状态集 : F 是 可接受状态 , 是 Q 的子集 , 记做 F ⊆ Q F , 与 F 可接受状态相对的是不可接受状态 ;
二、确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 等价
确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ;
确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ;
确定性有限自动机 给定一个输入 , 其输出时唯一的 ;
非确定性有限自动机的定义 包含 确定性有限自动机的 定义中 ;
NFA 的后继状态 可以是 0 00 个 , 1 11 个 或 多个 , DFA 每个状态只能有 1 11 个后继状态 ;
确定性有限自动机 ( DFA ) 就是 特殊的 非确定性有限自动机 ( NFA ) ;
可以证明非确定性有限自动机 ( NFA ) , 必定有一个 确定性有限自动机 ( DFA ) 与其等价 ;
三、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA ) 示例
正确的图片 :
下图绘制错误 , 暂时作废 , 看第一张图片 ;
上图绘制错误 , 暂时作废 , 看第一张图片 ;
字符集 : Σ = { a , b }
将上述 非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA ) , 需要将非确定性消除 , 只剩下确定性因素 ;
转换过程 使用特定算法实现 , 下面会详细描述该算法 ;
表格 : 绘制一个表格 , 表格列分别是 a , b 确定性有限自动机可以使用表格来表示 ;
开始状态分析 : 上述非确定性有限自动机开始状态 1 , 但是有一个 ε 空字符 , 指向 3状态 , 读取到空字符 ε 后会无条件跳转到 后继状态 3 , 因此 该自动机有 2个开始状态 ;
开始状态确定 : { 1 , 3 } , 将开始状态看做一个集合 , 将这两个状态组成的集合看做一个新的状态 ,
四、NFA 转 DFA ( 1 ) 开始状态 读取 a 字符 后继状态分析
表格 第 2 行 第 2 列 :
1 . 数值含义 : 该位置的含义是 { 1 , 3 } 开始状态下 , 读取 字符 a 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 1状态下读取 a 字符后的后继状态 , 3 状态下读取 a 字符后的后继状态 ;
① 1 状态下读取 a字符是空集 { ∅ }
② 3 状态下读取 a 字符后继状态是 1 , 此时 1 状态又可以无条件跳转到 3 状态 , 可以与 1 状态并列 , 此时 3 状态 读取 a 字符的后继状态是 { 1 , 3 };
3 . 后继状态取并集 : 将上述的 两个 后继状态 { ∅ } 和 { 1 , 3 } , 取并集 , 就是 { 1 , 3 } 状态下读取 a 字符的后继状态 , 取并集的结果是 { 1 , 3 } ;
第 2 行 第 2 列 的 值是 { 1 , 3 } , 代表 { 1 , 3 } 状态下读取 字符 a , 后继状态是 { 1 , 3 } 状态 ;
五、NFA 转 DFA ( 2 ) 开始状态 读取 b 字符 后继状态分析
表格 第 2 行 第 3 列 :
1 . 数值含义 : 该位置的含义是 { 1 , 3 } 开始状态下 , 读取 字符 b之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 1 状态下读取 b 字符后的后继状态 , 3 状态下读取 b 字符后的后继状态 ;
① 1 状态下读取 b 字符 后继状态是 { 2 } ;
② 3 状态下读取 b 字符后继状态是 { ∅ } 空集 ;
3 . 后继状态取并集 : 将上述的 两个 后继状态 { 2 } 和 { ∅ } , 取并集 , 就是 { 1 , 3 } 状态下读取 b 字符的后继状态 , 取并集的结果是 { 2 } ;
第 2 行 第 3 列 的 值是 { 2 } , 代表 { 1 , 3 } 状态下读取 字符 b , 后继状态是 { 2 } 状态 ;
开始集合 { 1 , 3 } , 读取 a 字符 , 读取 b 字符的后继状态 , 分析完毕 ;
六、NFA 转 DFA ( 3 ) 选取第二个状态进行分析
选取原则 : 没有出现过的状态 , 都要进行分析 ;
开始分析后续状态 , 第一个后继状态是 { 1 , 3 } 就是开始状态 , 已经分析过了 , 不再考虑 , 开始分析 { 2 } 状态 ;
七、NFA 转 DFA ( 4 ) 2 22 状态读取 a 字符后续状态分析
表格 第 3 行 第 2 列 :
1 . 数值含义 : 该位置的含义是 { 2 } 开始状态下 , 读取 字符 a 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 { 2 } 状态下读取 a 字符后的后继状态 是 { 2 , 3 } ;
3 . 后继状态 : 第 3 行 第 2 列 的 值是 { 2 , 3 } , 代表 { 2 } 状态下读取 字符 a , 后继状态是 { 2 , 3 } 状态 ;
八、NFA 转 DFA ( 5 ) 2 22 状态读取 b 字符后续状态分析
表格 第 3 行 第 3 列 :
1 . 数值含义 : 该位置的含义是 { 2 } 开始状态下 , 读取 字符 b 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 { 2 } 状态下读取 b bb 字符后的后继状态 是 { 3 } ;
3 . 后继状态 : 第 3 行 第 3 列 的 值是 { 3 } , 代表 { 2 } 状态下读取 字符 b , 后继状态是 { 3 } 状态 ;
九、NFA 转 DFA ( 6 ) 选取后续需要分析的状态
选取原则 : 没有出现过的状态 , 都要进行分析 ;
{ 2 , 3 } 和 { 3 } 状态都是分析 { 2 } 状态的后继状态时新出现的状态 , 因此将这两个状态加入表格中 , 进行分析 ;
加入两个状态后 , 最新表格如下 :
下面开始分析后续内容 ;
十、NFA 转 DFA ( 7 ) { 2 , 3 } 状态 读取 a 字符 后继状态分析
表格 第 4 行 第 2 列 :
1 . 数值含义 : 该位置的含义是 { 2 , 3 } 开始状态下 , 读取 字符 a 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 2 状态下读取 a 字符后的后继状态 , 3 状态下读取 a 字符后的后继状态 ;
① 2 状态下读取 a 字符 后继状态是 { 2 , 3 } ;
② 3 状态下读取 a 字符后继状态是 { 1 , 3 } , 这里只要能到达状态 1 , 便需要无条件跳转到状态 3 , 因为 1 状态下读取空字符 ε 即可转为 3 状态 , 因此 1 , 3 状态并列 ;
3 . 后继状态取并集 : 将上述的 两个 后继状态 { 2 , 3 } 和 { 1 , 3 } , 取并集 , 就是 { 2 , 3 } 状态下读取 a 字符的后继状态 , 取并集的结果是 { 1 , 2 , 3 } ;
第 4 行 第 2 列 的 值是 { 1 , 2 , 3 } , 代表 { 2 , 3 } 状态下读取 字符 a , 后继状态是 { 1 , 2 , 3 } 状态 ;
十一、NFA 转 DFA ( 8 ) { 2 , 3 } 状态 读取 b 字符 后继状态分析
表格 第 4 行 第 3 列 :
1 . 数值含义 : 该位置的含义是 { 2 , 3 } 开始状态下 , 读取 字符 b 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 2 状态下读取 b 字符后的后继状态 , 3 状态下读取 b 字符后的后继状态 ;
① 2 状态下读取 b 字符 后继状态是 { 3 } ;
② 3 状态下读取 b 字符后继状态是 { ∅ } ;
3 . 后继状态取并集 : 将上述的 两个 后继状态 { 3 } 和 { ∅ } , 取并集 , 就是 { 2 , 3 } 状态下读取 b 字符的后继状态 , 取并集的结果是 { 3 } ;
第 4 行 第 3 列 的 值是 { 3 } , 代表 { 2 , 3 } 状态下读取 字符 b , 后继状态是 { 3 } 状态 ;
十二、NFA 转 DFA ( 9 ) 选取后续需要分析的状态
选取原则 : 没有出现过的状态 , 都要进行分析 ;
{ 1 , 2 , 3 } 是 新出现的状态 , 因此将这两个状态加入表格中 , 进行分析 ;
加入该状态后 , 最新表格如下 :
下面开始分析后续内容 ;
十三、NFA 转 DFA ( 10 ) { 3 } 状态 读取 a 字符 后继状态分析
表格 第 5 行 第 2 列 :
1 . 数值含义 : 该位置的含义是 { 3 } 开始状态下 , 读取 字符 a 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 3 状态下读取 a 字符后的后继状态 是 { 1 , 3 }
3 . 后继状态 : 第 5 行 第 2 列 的 值是 { 1 , 3 } , 代表 { 3 } 状态下读取 字符 a , 后继状态是 { 1 , 3 } 状态 ;
十四、NFA 转 DFA ( 11 ) { 3 } 状态 读取 b 字符 后继状态分析
表格 第 5 行 第 3 列 :
1 . 数值含义 : 该位置的含义是 { 3 } 开始状态下 , 读取 字符 b 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 3 状态下读取 b 字符后的后继状态 是 { ∅ }
3 . 后继状态 : 第 5 行 第 3 列 的 值是 { ∅ } , 代表 { 3 } 状态下读取 字符 b , 后继状态是 { ∅ } 状态 ;
十五、NFA 转 DFA ( 12 ) { 1 , 2 , 3 }状态 读取 a 字符 后继状态分析
表格 第 6 行 第 2 列 :
1 . 数值含义 : 该位置的含义是 { 1 , 2 , 3 } 开始状态下 , 读取 字符 a 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 1 状态下读取 a 字符后的后继状态 , 2 状态下读取 a 字符后的后继状态 , 3 状态下读取 a 字符后的后继状态 ;
① 1 状态下读取 a 字符 后继状态是 { ∅ } ;
② 2 状态下读取 a 字符 后继状态是 { 2 , 3 } ;
③ 3 33 状态下读取 a aa 字符后继状态是 { 1 , 3 } , 这里只要能到达状态 1 , 便需要无条件跳转到状态 3 , 因为 1 状态下读取空字符 ε 即可转为 3 状态 , 因此 1 , 3 状态并列 ;
3 . 后继状态取并集 : 将上述的 3 个 后继状态 { ∅ } , { 2 , 3 } 和 { 1 , 3 } , 取并集 , 就是 { 1 , 2 , 3 } 状态下读取 a 字符的后继状态 , 取并集的结果是 { 1 , 2 , 3 } ;
第 6 行 第 2 列 的 值是 { 1 , 2 , 3 } , 代表 { 1 , 2 , 3 } 状态下读取 字符 a , 后继状态是 { 1 , 2 , 3 } 状态 ;
十六、NFA 转 DFA ( 13 ) { 1 , 2 , 3 } 状态 读取 b 字符 后继状态分析
表格 第 6 行 第 3 列 :
1 . 数值含义 : 该位置的含义是 { 1 , 2 , 3 } 开始状态下 , 读取 字符 b 之后的后续状态集 ;
2 . 后继状态分析 : 分别考虑 1 状态下读取 b 字符后的后继状态 , 2 状态下读取 b 字符后的后继状态 , 3 状态下读取 b 字符后的后继状态 ;
① 1 状态下读取 b 字符 后继状态是 { 2 } ;
② 2 状态下读取 a 字符 后继状态是 { 3 } ;
③ 3 状态下读取 a 字符后继状态是 { ∅ } ;
3 . 后继状态取并集 : 将上述的 3 个 后继状态 { 2 } , { 3 }和 { ∅ } , 取并集 , 就是 { 1 , 2 , 3 } 状态下读取 b 字符的后继状态 , 取并集的结果是 { 2 , 3 } ;
十七、NFA 转 DFA ( 14 ) 结果分析
1 . 消除不确定性 : 下面的表格就是将 非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA ) 的结果 , 将状态集合当做一个新的状态 , 新状态由之前的 NFA 中的不同状态组合而来 , 由此消除不确定性 ;
2 . 定义开始状态 : 将 { 1 , 3 } 定义成开始状态 ;
3 . 定义接收状态 : 原来的 非确定性有限自动机 ( NFA ) 中 1 是接受状态 , 在新的 确定性有限自动机 ( DFA ) 中 , 只要状态集合中包含 1 , 那么该状态集合就是 接受状态 , 因此这里 { 1 , 3 } 和 { 1 , 2 , 3 } 两个状态集 代表的 新状态 是接受状态 ;
