【计算理论】计算理论总结 ( 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ) ★★

2023-03-28 20:05:58 浏览数 (1)

文章目录

  • 一、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA )
  • 二、转换方法与要点

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

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

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

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

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

NFA 的后继状态 可以是

0

个 ,

1

个 或 多个 , DFA 每个状态只能有

1

个后继状态 ;

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

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

参考博客 :

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

二、转换方法与要点

1. 转换方法 :

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

列出所有的 分支步骤 ,

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

此时就生成了 新的状态 ,

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

2. 转换要点 :

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

情况一 : 状态有

rm varepsilon

无条件跳转 , 如下图的

1

状态 , 会无条件跳转到

3

状态 , 此时就会出现两个后续状态

rm { 1, 3 }

,

情况二 : 读取同样的字符 , 有两个后继状态 , 如

2

状态下读取

rm a

字符 , 会跳转到

2

状态和

3

状态 , 因此其后继状态是

rm { 2, 3 }

,

情况三 : 计算出现新状态后 , 新状态的后继状态 , 一般也是一个集合 , 当计算

rm { 1, 3 }

的后续状态时 , 会分别计算集合中的两个状态分别读取

rm a

字符的后继状态 , 取并集 ;

② 新状态的计算机制 : 如果生成了一个新的状态 ,

rm { 1, 3 }

, 如果要计算其后继状态时 , 就需要分别计算

1

和

3

的后继状态, 然后取并集 ;

③ 空集 : 在推演计算时 , 有可能会出现空集 , 如

rm { 3 }

状态读取

rm b

字符的后继状态没有 , 就是空集 ;

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

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

5 . 后继状态有

rm varepsilon

无条件跳转 : 如果读取字符后跳转的 后继状态有

rm varepsilon

无条件跳转 , 则该后继状态会是两个状态的集合 , 如 :

rm { 3 }

状态读取

rm a

字符跳转到

1

状态 , 而

1

状态无条件跳转到

3

状态 , 则后继状态是

rm {1, 3}

;

参考博客 :

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

0 人点赞