一、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA )

确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ;

确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ;

确定性有限自动机 给定一个输入 , 其输出时唯一的 ;

非确定性有限自动机的定义 包含 确定性有限自动机的 定义中 ;

NFA 的后继状态 可以是 $0$ 个 , $1$ 个 或 多个 , DFA 每个状态只能有 $1$ 个后继状态 ;

确定性有限自动机 ( DFA ) 就是 特殊的 非确定性有限自动机 ( NFA ) ;

可以证明非确定性有限自动机 ( NFA ) , 必定有一个 确定性有限自动机 ( DFA ) 与其等价 ;

参考博客 :

• 【计算理论】非确定性有限自动机 ( 计算过程 | 计算树 | 确定可接受字符串 | 设计非确定性有限自动机 | 空字符 )
• 【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )

二、转换方法与要点

1. 转换方法 :

从 起始状态 开始推演运行 ,

列出所有的 分支步骤 ,

注意 计算分叉节点 , 会产生多个后续状态 ,

此时就生成了 新的状态 ,

这些新的状态就是非确定性有限自动机 转换成的 确定性有限自动机的 新状态 ;

2. 转换要点 :

① 新状态生成时机 : 有两种情况会出现计算分支 ,

情况一 : 状态有 $\epsilon$ 无条件跳转 , 如下图的 $1$ 状态 , 会无条件跳转到 $3$ 状态 , 此时就会出现两个后续状态 $\{1,3\}$ ,

情况二 : 读取同样的字符 , 有两个后继状态 , 如 $2$ 状态下读取 $\mathrm{a}$ 字符 , 会跳转到 $2$ 状态和 $3$ 状态 , 因此其后继状态是 $\{2,3\}$ ,

情况三 : 计算出现新状态后 , 新状态的后继状态 , 一般也是一个集合 , 当计算 $\{1,3\}$ 的后续状态时 , 会分别计算集合中的两个状态分别读取 $\mathrm{a}$ 字符的后继状态 , 取并集 ;

② 新状态的计算机制 : 如果生成了一个新的状态 , $\{1,3\}$ , 如果要计算其后继状态时 , 就需要分别计算 $1$ 和 $3$ 的后继状态, 然后取并集 ;

③ 空集 : 在推演计算时 , 有可能会出现空集 , 如 $\{3\}$ 状态读取 $\mathrm{b}$ 字符的后继状态没有 , 就是空集 ;

3. 接受状态 : 如果最终的 DFA 的新状态集合中 , 包含 NFA 的接受状态 , 那么该新状态就是接受状态 ;

4. 空集 : 如果其中有空集 , 那么将空集也当做一个状态 , 空集状态下读取任何字符都是空集 ;

5 . 后继状态有 $\epsilon$ 无条件跳转 : 如果读取字符后跳转的 后继状态有 $\epsilon$ 无条件跳转 , 则该后继状态会是两个状态的集合 , 如 : $\{3\}$ 状态读取 $\mathrm{a}$ 字符跳转到 $1$ 状态 , 而 $1$ 状态无条件跳转到 $3$ 状态 , 则后继状态是 $\{1,3\}$ ;

参考博客 :

• 【计算理论】非确定性有限自动机 ( 计算过程 | 计算树 | 确定可接受字符串 | 设计非确定性有限自动机 | 空字符 )
• 【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111301379