《编译原理》课后习题答案第四章 第4章词法分析 第1愿 构造下列正规式相应的DFA (1)101101 （2)11010*11010)*1)*0 (3)a((ab)"jab*a)*b （4)b(ab)*bb)*ab 答案： (I)先构造NFA: -080-o+@ 用子集法将NFA确定化 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为终态。 X A A B B c B A D B )FA的状态图： -088已 盛威网(ww.snwei.com)专业的计算机学习同站
《编译原理》课后习题答案第四章 第 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 的状态图：: 盛威网（www.snwei.com）专业的计算机学习网站 1
《编译原理》课后习题答案第四章 (2)先构造NFA: 用子集法将NFA确定化 E 0 1 To=X A A ABFL T=ABFL CG Y CG CGJ T=Y TCGJ DH DH DH K ABFKL T=DH EI EI AbEFIL Ts=ABFKL CG T6=ABEFIL EJY CG EJY ABEFGJLY TABEEGILY EHY CGK EHY ABEFHLY CGK ABCFGJKL T=ABEFHLY EY CGI ABEFLY CGI CGJI Ty=ABCFGJKL DHY CGK DHY DHY T1O=ABEFLY EY DHJ K DHJ DHJ Th2=DHY EI T=DHJ EIK EIK ABEFIKL T1=ABEFIKL EJY CG 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第四章 (2)先构造 NFA： X A 1 ε 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 盛威网（www.snwei.com）专业的计算机学习网站 2
《编译原理》课后习题答案第四章 将To、T1、T2、T3、T4、T5、T6、T、Tg、T、T0、T1、T12、T1、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 2 3 2 3 4 4 6 2 3 6 7 3 7 8 9 8 10 11 12 9 10 10 3 11 13 5 12 6 13 4 7 3 5 4)1 00 盛成网(www.snwei.com)专业的计算机学习网站 3
《编译原理》课后习题答案第四章 将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 盛威网（www.snwei.com）专业的计算机学习网站 3
《编译原理》课后习题答案第四章 (3)先构造NFA: 先构造NFA: ∩a,b B) 用子集法将NFA确定化 e To=X A A ABCD T=ABCD BE BY BE ABCDE BY ABCDY T-ABCDE BEF BEY BEE ABCDEE ABCDEY BE BY T=ABCDE BEY Ts=ABCDEY BEF BEY 将T0、T、T、T、T4、T重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y 所以它们都为终态。 a b 0 1 3 3 2 3 4 4 5 4 aa ②n4 盛咸网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第四章 (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 b 1 3 2 a 5 4 a b a b a b a b 盛威网（www.snwei.com）专业的计算机学习网站 4
《编译原理》课后习题答案第四章 (4)先构造NFA: e e ,a⊙b⊙ A) 用子集法将NFA确定化： b X X To=X A T=ABDEF CI G LCI c G G T-CI DY DY ABDEFY T=G H H ABEFH T-ABDEFY G Ts=ABEFH CI G 将T0T、T2、T、T4、T重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y 所以它为终态。 b 0 2 3 2 4 3 5 4 2 3 2 3 DFA的状态图： 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第四章 (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 的状态图： 盛威网（www.snwei.com）专业的计算机学习网站 5