文章目录
一、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA )
二、转换方法与要点
一、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA )
确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ;
确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ;
确定性有限自动机 给定一个输入 , 其输出时唯一的 ;
非确定性有限自动机的定义 包含 确定性有限自动机的 定义中 ;
NFA 的后继状态 可以是 0 00 个 , 1 11 个 或 多个 , DFA 每个状态只能有 1 11 个后继状态 ;
确定性有限自动机 ( DFA ) 就是 特殊的 非确定性有限自动机 ( NFA ) ;
可以证明非确定性有限自动机 ( NFA ) , 必定有一个 确定性有限自动机 ( DFA ) 与其等价 ;
参考博客 :
【计算理论】非确定性有限自动机 ( 计算过程 | 计算树 | 确定可接受字符串 | 设计非确定性有限自动机 | 空字符 )
【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )
二、转换方法与要点
1. 转换方法 :
从 起始状态 开始推演运行 ,
列出所有的 分支步骤 ,
注意 计算分叉节点 , 会产生多个后续状态 ,
此时就生成了 新的状态 ,
这些新的状态就是非确定性有限自动机 转换成的 确定性有限自动机的 新状态 ;
2. 转换要点 :
① 新状态生成时机 : 有两种情况会出现计算分支 ,
情况一 : 状态有 ε \rm \varepsilonε 无条件跳转 , 如下图的 1 11 状态 , 会无条件跳转到 3 33 状态 , 此时就会出现两个后续状态 { 1 , 3 } \rm \{ 1, 3 \}{1,3} ,
情况二 : 读取同样的字符 , 有两个后继状态 , 如 2 22 状态下读取 a \rm aa 字符 , 会跳转到 2 22 状态和 3 33 状态 , 因此其后继状态是 { 2 , 3 } \rm \{ 2, 3 \}{2,3} ,
情况三 : 计算出现新状态后 , 新状态的后继状态 , 一般也是一个集合 , 当计算 { 1 , 3 } \rm \{ 1, 3 \}{1,3} 的后续状态时 , 会分别计算集合中的两个状态分别读取 a \rm aa 字符的后继状态 , 取并集 ;
② 新状态的计算机制 : 如果生成了一个新的状态 , { 1 , 3 } \rm \{ 1, 3 \}{1,3} , 如果要计算其后继状态时 , 就需要分别计算 1 11 和 3 33 的后继状态, 然后取并集 ;
③ 空集 : 在推演计算时 , 有可能会出现空集 , 如 { 3 } \rm \{ 3 \}{3} 状态读取 b \rm bb 字符的后继状态没有 , 就是空集 ;
3. 接受状态 : 如果最终的 DFA 的新状态集合中 , 包含 NFA 的接受状态 , 那么该新状态就是接受状态 ;
4. 空集 : 如果其中有空集 , 那么将空集也当做一个状态 , 空集状态下读取任何字符都是空集 ;
5 . 后继状态有 ε \rm \varepsilonε 无条件跳转 : 如果读取字符后跳转的 后继状态有 ε \rm \varepsilonε 无条件跳转 , 则该后继状态会是两个状态的集合 , 如 : { 3 } \rm \{ 3 \}{3} 状态读取 a \rm aa 字符跳转到 1 11 状态 , 而 1 11 状态无条件跳转到 3 33 状态 , 则后继状态是 { 1 , 3 } \rm \{1, 3\}{1,3} ;
参考博客 :
【计算理论】非确定性有限自动机 ( 计算过程 | 计算树 | 确定可接受字符串 | 设计非确定性有限自动机 | 空字符 )
【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )
