《编译原理》课后习题答案第四章
盛威网（ ww w .snwei.com ）专业的计算机学习网站
1
第
4
章 词法分析
第
1
题
构造下列正规式相应的 DFA.
（１）
1(0|1)
*101
（２） １
(1010*|1(010)*1
）
*0
（３）
a((a|b)*|ab*a)*b
（４）
b((ab)*|bb)*ab
答案：
(1)
先构造
NFA
：
用子集法将
NFA
确定化
. 0 1
X . A
A A AB
AB AC AB
AC A ABY
ABY AC AB
除
X
，
A
外，重新命名其他状态，令
AB
为
B
、
AC
为
C
、
ABY
为
D
，因为
D
含有
Y
（
NFA
的终态），所以
D
为终态。
. 0 1
X . A
A A B
B C B
C A D
D C B
DFA
的状态图：
:
