《编译原理》课后习题答案第四章 第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
《编译原理》课后习思答案第四章 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第四章 0 b b 1 2 a 4 5 3 b b a b a b 盛威网（www.snwei.com）专业的计算机学习网站 6
《编译原理》课后习题答案第四章 第2题 己知NFA=(x2),0,M,),其中：M0,M=M0F, M,1-,M,1=中，M2I)=,构造相应的DFA。 答案： 先构造其矩阵 0 1 7 x xy x,2 y 用子集法将NFA确定化： 0 1 2 x Z xZ y XZ xZ XV y xy xyz x xyz xyz y 将x、z、 y重新命名，分别用A、B、C、D、E、F表示，因为B、C、F 中含有，所以它为终态。 0 1 B D E F F DFA的状态图 D 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第四章 第２题 已知 NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}， M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的 DFA。 答案： 先构造其矩阵 0 1 x z x y x,y z x,z y 用子集法将 NFA 确定化： 0 1 x z x z xz y xz xz xy y xy xy xyz x xyz xyz xy 将 x、z、xz、y、xy、xyz 重新命名，分别用 A、B、C、D、E、F 表示。因为 B、C、F 中含有 z，所以它为终态。 0 1 A B A B C D C C E D E E F A F F E DFA 的状态图： 盛威网（www.snwei.com）专业的计算机学习网站 7 A 0 1 0 F E D 0 B 1 0 1 0 1 0 1 C
《编译原理》课后习思答案第四章 第3题 将下图确定化 0 0 0,1 Q) ⊙ 答案： 用子集法将NFA确定化： 0 s VQ QU VQ VZ QU QU QUZ VZ Z Z w QUZ QUZ Z Z Z 重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 0 s A B B B D E c F F D F E C E F DFA的状态图： 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第四章 第 3 题 将下图确定化： 答案： 用子集法将 NFA 确定化： . 0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z . QUZ VZ QUZ Z Z Z 重新命名状态子集，令 VQ 为 A、QU 为 B、VZ 为 C、V 为 D、QUZ 为 E、Z 为 F。 . 0 1 S A B A C B B D E C F F D F . E C E F F F DFA 的状态图： 盛威网（www.snwei.com）专业的计算机学习网站 8
《编译原理》课后习趣答案第四章 a) D 第4题 将下图的()和(b)分别确定化和最小化： ·-@600 oo 答案： 初始分划得 10:终态组0，非终态组{1,234,5) 对非终态组进行审查： f123.4.5ac0.1.3.51 而0,13.51既不属于01，也不属于12,3,4,5 :4a0，所以得到新分划 1:{0,4,12,35 对{1,235！进行审查： 15)bc4} 2.31b二{1.2,3,5，故得到新分划 2:{0,{4,1,5,2,3y {1,5}ae{l,5} 2,3}a二{1,3}，故状态2和状态3不等价，得到新分划 13:{0,{2,{3,{43,{L,5} 这是最后分划了 盛成网(www.snwei.com)专业的计算机学习网站 9
《编译原理》课后习题答案第四章 第 4 题 将下图的（a）和（b）分别确定化和最小化： 答案： 初始分划得 Π0：终态组{0}，非终态组{1,2,3,4,5} 对非终态组进行审查： {1,2,3,4,5}a {0,1,3,5} 而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5} ∵{4} a {0}，所以得到新分划 Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查： ∵{1,5} b {4} {2,3} b {1,2,3,5}，故得到新分划 Π2：{0}，{4}，{1, 5}，{2,3} {1, 5} a {1, 5} {2,3} a {1,3}，故状态 2 和状态 3 不等价，得到新分划 Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了 盛威网（www.snwei.com）专业的计算机学习网站 9
《编译原理》课后习答案第四章 最小DFA: 2。③） aa 4 第5题 构造一个DA,它接收2=0,1)上所有满足如下条件的字符串：每个1都有0直接跟在 右边。并给出该语言的正规式。 答案： 按题意相应的正规表达式是(0*10)*0*，或0*(O11O)*0*构造相应的DFA,首先构造NFA为 08:8 a 用子集法确定化： 1 {X0,1,3,Y t0,l,3,Y9 2 0,1,3,Y 0,1,3,Y 2} {1,3,Y (13.Y) 13,Y 2 重新命名状态集： 0 23 2 4 DFA的状态图： 盛威网(ww.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第四章 最小 DFA： 第 5 题 构造一个 DFA，它接收 Σ={0,1}上所有满足如下条件的字符串：每个 1 都有 0 直接跟在 右边。并给出该语言的正规式。 答案： 按题意相应的正规表达式是(0*10)*0*，或 0*(0 | 10)*0* 构造相应的 DFA，首先构造 NFA 为 用子集法确定化： I I0 I1 {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} {0,1,3,Y} {0,1,3,Y} {1,3,Y} {1,3,Y} {2} {2} {2} 重新命名状态集： S 0 1 1 2 3 4 2 2 4 4 3 3 3 DFA 的状态图： 盛威网（www.snwei.com）专业的计算机学习网站 10