《编译原理》课后习题答案第四章
先构造 NFA：(2) X T0=X A T1= ABFL Y CG T2= Y T3= CGJ DH K T4= DH EI T5= ABFKL T6= ABEFIL EJY T7= ABEFGJLY EHY CGK T8= ABEFHLY EY CGI T9= ABCFGJKL DHY T10= ABEFLY T11= CGJI 0 ε X 1 A ε ε F B 1 C 0 ε 1 G 0 H 1 I 0 ε J 1 K D 1 E ε L ε ε 0 Y 用子集法将 NFA 确定化 ε X ABFL Y CGJ DH ABFKL ABEFIL ABEFGJLY ABEFHLY ABCFGJKL ABEFLY CGJI DHY 0 Y DH Y EJY EHY EY DHY EY DHJ 1 A CG K EI CG CG CGK CGI CGK CG K 2
盛威网（www.snwei.com）专业的计算机学习网站
《编译原理》课后习题答案第四章
DHJ T12= DHY T13= DHJ EIK T14= ABEFIKL DHJ ABEFIKL EJY EI EIK 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 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 2 7 8 10 12 10 13 7 1 1 3 5 6 3 3 9 11 9 3 5 6 14 3
盛威网（www.snwei.com）专业的计算机学习网站
3
《编译原理》课后习题答案第四章
0 1 1 1 (3) 先构造 NFA： 先构造 NFA： ε a,b ε B ε C b Y X a A ε b ε D a E a F ε
用子集法将 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 盛威网（www.snwei.com）专业的计算机学习网站
4
《编译原理》课后习题答案第四章
2 3 4 5 0
(4) 先构造 NFA： ε ε X b A ε
用子集法将 NFA 确定化： X T0=X A T1=ABDEF CI G T2=CI DY T3=G ε X CI G 4 2 4 4 b
3 a a 4 5 3 5 5 b a 1 a 2 b b 5 a a b a C
ε B b ε F b G b H ε ε D ε E a I b Y a CI b A G DY H 5
ABDEF ABDEFY
盛威网（www.snwei.com）专业的计算机学习网站
《编译原理》课后习题答案第四章
H T4=ABDEFY T5=ABEFH
ABEFH CI CI G G 将T0、T1、T2、T3、T4、T5重新命名，分别用 0、1、2、3、4、5 表示。因为 4 中含有Y， 所以它为终态。
0 1 2 3 4 5
DFA 的状态图： 0 b 1 a 2 b a a 4 b 3 b b 5 b a 2 2 2 b 1 3 4 5 3 3
盛威网（www.snwei.com）专业的计算机学习网站
6
编译原理课后习题答案+清华大学出版社第二版
