清华大学第二版编译原理答案
（３） 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 的状态图：: (2)先构造NFA： X 1 A ε B
1 C 0 D 1 E 0
ε
F 1 G 0 H 1 I 0 J 1 K L ε ε 0 Y ε ε ε ε
用子集法将NFA 确定化 ε 0 1 X X T0=X A A ABFL
T1= ABFL Y CG Y Y CG CGJ T2= Y
清华大学第二版编译原理答案
T3= CGJ DH K DH DH K ABFKL T4= DH EI EI ABEFIL
T5= ABFKL Y CG T6= ABEFIL EJY CG EJY ABEFGJLY
T7= ABEFGJLY EHY CGK EHY ABEFHLY CGK ABCFGJKL
T8= ABEFHLY EY CGI EY ABEFLY CGI CGJI
T9= ABCFGJKL DHY CGK DHY DHY
T10= ABEFLY EY CG T11= CGJI DHJ K DHJ DHJ T12= DHY EI T13= DHJ EIK EIK ABEFIKL
T14= ABEFIKL EJY CG
将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别用0、
1、2、3、4、5、6、7、8、9、10、11、12、13、14 表示。因为2、7、8、10、12 中含有Y， 所以它们都为终态。 0 1 0 1 1 2 3 2 3 4 5 4 6 5 2 3 6 7 3 7 8 9 8 10 11 9 12 9 10 10 3 11 13 5 12 6 13 14 14 7 3 0 1 0
清华大学第二版编译原理答案
12 1 2 7 10 8 3 4 5 6 9
11 13 14 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1
(3) 先构造NFA： 先构造NFA： X a A ε B a,b ε
D a E a F C ε Y ε ε b
清华大学第二版编译原理答案
ε b
用子集法将NFA 确定化 ε a b X X T0=X A A ABCD
T1=ABCD BE BY BE ABCDE BY ABCDY
T2=ABCDE BEF BEY BEF ABCDEF BEY ABCDEY T3=ABCDY BE BY T4=ABCDEF BEF BEY T5=ABCDEY BEF BEY
将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5 表示。因为3、5 中含有Y，
所以它们都为终态。 a b 0 1 1 2 3 2 4 5 3 2 3 4 4 5 5 4 5 0 a 1 b 3 2 a 5 a 4 b a b a b a b
(4) 先构造NFA： X A b ε B a
F b G b H
清华大学第二版编译原理答案
E ε Y a
ε
C D b ε I b ε ε ε ε
用子集法将NFA 确定化： ε a b X X T0=X A A ABDEF
T1=ABDEF CI G CI CI G G
T2=CI DY DY ABDEFY T3=G H H ABEFH
T4=ABDEFY CI G T5=ABEFH CI G
将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5 表示。因为4 中含有Y， 所以它为终态。 a b 0 1 1 2 3 2 4 3 5 4 2 3 5 2 3
DFA 的状态图： 0 b 1 b 2 a 4 5 3 b b a