[课本]正规式转NFA,NFA转换为DFA以及DFA化简 |
您所在的位置：网站首页 › nfa转化为dfa例题详解 › [课本]正规式转NFA,NFA转换为DFA以及DFA化简 |
[课本]正规式转NFA,NFA转换为DFA以及DFA化简
|
文章目录
正规式转NFANFA -> DFA定义例3.3 NFA 转换为 DFA构造过程重新命名
例 3.6 化简 DFA
教材使用《程序设计语言编译原理》-3版，作者：陈火旺、刘春林等。 用自己的话把教材上的例题复现了一遍，如有不足，请指教。 NFA ：非确定有限自动机； DFA ：确定有限自动机； 正规式转NFA
涉及到课本 P49~P50 讲解的子集法——把 NFA 确定为 DFA 的方法。(下面再解释解释) 定义 M : NFAM’ : 最终得到的 NFAM’’ : DFA 假定 I 是 M’ 的状态集的子集，ε_CLOSURE(I) : 由 ε 弧连接起来的一个连通分量 I 的 ε 闭包，包括 I 本身，也包括从其中任意一个状态元素 q 通过任意条 ε 弧可以到达的状态 q’； 图3.6 举例：像 ε_CLOSURE({X}) = {X, 5, 1}， ε_CLOSURE({2}) = {2, 6, Y}， 就是由 ε 弧连接起来的一个连通分量；Ia : 由 a 弧连接起来的一个连通分量 Ia = ε_CLOSURE(J)，J 中的状态 q’ 是从 I 中任意一个状态 q 通过一条 a 弧可以达到的状态，同时不要忘记通过任意条 ε 弧 到达的状态； 图3.6 举例 : {5, 3, 1}a = {5, 3, 1, 2, 6, 7}， 分析过程：
原状态通过 a 弧到达的状态553213
得到状态集合：{5, 3, 2}； 原状态通过 ε 弧到达的状态513\26, Y最后得到状态集合：{5, 3, 1, 2, 6, 7}； 注意，每个状态，特别是终态，都可以看作有一条 ε 弧连接自己，所以终态只能读取 ε，其它的读取不了。上面有些状态集合里含有终态 Y ，是由前面的状态通过 ε 弧达到的。 例3.3 NFA 转换为 DFA正规式 (a|b)*(aa|bb)(a|b)* 对应的 NFA 如图 3.6 所示，其中 X 为初态，Y 为终态。按照上述过程(子集法)构造出来的状态转换矩阵见表 3.3 表 3.3 对应于例 3.3 中正规式的状态转换矩阵 构造过程把初始状态 X 的 ε 闭包，即 ε_CLOSURE({X})， 现在记为 I，放在第一行第一列，求出Ia， Ib，将出现在右边列(除最左边一列外的所以列)，但是没有出现在最左边列的状态集合，添加到最左边列中，重复操作，直到右边列中出现的所有状态集都在最左边列出现过。
由表 3.4 画出对应的状态图 (图 3.8)： 化简图 3.8 表示的 DFA； 首先把 M 的状态分成两组 ：终态组，非终态组； |
就这么简单。。。
图3.6 非确定有限自动机
对表 3.3 中的所有状态子集重新命名，其中含有原终态 Y 的新状态也是终态，标记上双圆圈，得到表 3.4 所列的状态转换矩阵； 
表 3.4 对表 3.3 中状态子集重新命名后的状态转换矩阵
图 3.8 未化简的 DFA
得到化简后的图像 (图 3.5)： 
图 3.5 状态转换图【本文地址】
今日新闻 |
推荐新闻 |