不确定的有限自动机转为确定的自动机
可以识别语言(a|b)*ab的NFA的 转换图如图示。
识别(a|b)*ab的NFA
转换表：每个状态一行，每个输入符号和
（如果需要的话）各占一列，表的第i行中符号a的条目是一个状态集合（说得更实际一些，是状态集合的指针），这是NFA在输入为a时，状态i所到达的状态集合。下图是对应的NFA的转换表。
状态
输入符号
a
b
0
{0,1}
{0}
1
{2}
2
转换表的优点是可以快速访问给定状态和字符的状态集，缺点是，当输入字母表较大，并且大多数转换是空集时，会占用大量的空间。
转换
例子
识别(a|b)*ab的NFA
这里输入字母表是{a,b},令A={0,1,2,4,7},
-closure(move(A,a)),在A中，只有2和7有a转换，分别转到3和8，因此move(A,a)={3,8}，故
-closure(move(A,a))=
-closure({3,8})
={1,2,3,4,6,7,8}，这是因为
-closure（3）={1,2,3,4,6,7}，并且
-closure（8）={8}，记
B={1,2,3,4,6,7,8}。于是，
。
从图中可看出，在A={0,1,2,4,7}中，只有状态4含b转换到5，故该DFA状态A的b转换到达
-closure(move(A,b))=
-closure（{5}）={1,2,4,5,6,7},记C={1,2,4,5,6,7}。
用新的没有标记的的集合B和C继续这个过程，最终会达到这样：所有的集合（即
DFA的所有状态）都已标记，因为10个状态的集合的不同子集只有
个，一个集合一旦标记就永远是标记的，所以到终止是肯定的。
对于状态B={1,2,3,4,6,7,8},只有2和7有有a转换，分别到3和8，
-closure(move(B,a))=
-closure({3,8})={1,2,3,4,6,7,8}.
同样，对状态B={1,2,3,4,6,7,8}，只有状态4和8有b转换，分别转到5和9，故
-closure(move(B,b))=
-closure({5,9})={1,2,4,5,6,7,9},记D={1,2,4,5,6,7,9}.
对C={1,2,4,5,6,7}，有2和7有a转换，分别转到3和8，因此move(C,a)={3,8}，故
-closure(move(C,a))=
-closure({3,8})={1,2,3,4,6,7,8}=B.
对C={1,2,4,5,6,7},只有状态4含b转换到5, 故
-closure(move(C,b))=
-closure（{5}）={1,2,4,5,6,7}=C.
对D={1,2,4,5,6,7,9}，只有2和7有a转换，分别转到3和8，因此move(D,a)={3,8}，故
-closure(move(D,a))=
-closure({3,8})={1,2,3,4,6,7,8}=B.
对D={1,2,4,5,6,7,9}，只有状态4含b转换到5, 故
-closure(move(D,b))=
-closure（{5}）={1,2,4,5,6,7}=C.
对本例，可实际构造出4个不同状态的集合是：
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
状态A是开始状态，状态D是仅有的接受状态，完整的转换表如下表：
NFA的转换表
状态
输入符号
a
b
A
B
C
B
B
D
C
B
C
D
B
C
对应的DFA的转换图为：
本文档为【将不确定的有限自动机转换为确定的自动机】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483