编译原理课后习题答案ch4

《编译原理课后习题答案ch4》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章词法分析第1题构造下列正规式相应的DFA.（１）1(0

2、1)*101（２）１(1010*

3、1(010)*1）*0（３）a((a

4、b)*

5、ab*a)*b（４）b((ab)*

6、bb)*ab答案：(1)先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:(2)先构造NFA：0ε101ε0εBCDELY1εXAεε10101FGHIJKεε用子集法将NF

7、A确定化ε01XXT0=XAAABFLT1=ABFLYCGYYCGCGJT2=YT3=CGJDHKDHDHKABFKLT4=DHEIEIABEFILT5=ABFKLYCGT6=ABEFILEJYCGEJYABEFGJLYT7=ABEFGJLYEHYCGKEHYABEFHLYCGKABCFGJKLT8=ABEFHLYEYCGIEYABEFLYCGICGJIT9=ABCFGJKLDHYCGKDHYDHYT10=ABEFLYEYCGT11=CGJIDHJKDHJDHJ？正确DHJGT12=DHYEIT13=DHJEIKEIKABEFIKLT14=ABEFIK

8、LEJYCG将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，所以它们都为终态。010112323454652367378981011912910103111351261314147310012101315110111461011079120000101108111314注意：这个题，也可以这样构造NFA（用最少的ε，但注意不能出错）：0013451ε10X1211600817方

9、法三：画NFA：1FG00E1110XAZ1εBCD010根据图画一个字母的表格：ε01XXAAAZBEBBCCCDDADDEEFAFFGGGEZZ根据上面的表格，画转换表：ε-closureεT1=AZ(T2)BE(T3)XXT2=ZAAT3=BECF(T4)A(T1)ZZT4=CFDG(T5)BEBET5=ADGZDE(T6)BE(T3)CFCFT6=ADEZZDF(T7)BEA(T8)DGADGT7=ADFZZD(T9)BEG(T10)ZDEZADET8=ABEZCF(T11)BEA(T8)ZDFZADFT9=ADZZD(T9)BE(T3)BEA

10、BEAT10=BEGCFE(T12)A(T1)ZDZADT11=CFZDG(T5)BEGBEGT12=CEFF(T13)DAG(T5)ZCFZCFT13=FG(T14)CFECFEFFT14=GE(T15)DAGDAGT15=EF(T13)A(T1)GGEEmove01T0=XA(T1)《编译原理》课后习题答案第四章根据上面的表，画出DFA图（略）盛威网（www.snwei.com）专业的计算机学习网站6《编译原理》课后习题答案第四章(3)先构造NFA：先构造NFA：a,bεεbεBCYbεXaAεaaDEFε用子集法将NFA确定化εabXXT0=XA

11、AABCDT1=ABCDBEBYBEABCDEBYABCDYT2=ABCDEBEFBEYBEFABCDEFBEYABCDEYT3=ABCDYBEBYT4=ABCDEFBEFBEYT5=ABCDEYBEFBEY将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y，所以它们都为终态。ab01123245323445545abb013aaaa24bbab5盛威网（www.snwei.com）专业的计算机学习网站7《编译原理》课后习题答案第四章注意：这个题，也可以这样构造NFA（用最少的ε，但注意不能出错）：a,b

12、ab013aa2a,b盛威网（www.snwei.com）专业的计算机学习网站8《编译原理》课后习题答案第四章(4)先构造NFA：εεabεεBCDbεEaIbXAεYbbεFGHε用子集法将NFA确定化：εabXXT0=XAAABDEFT1=ABDEFCIGCICIGGT2=CIDYDYABDEFYT3=GHHABEFHT4=ABDEFYCIGT5=ABEFHCIG将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y，所以它为终态。ab011232435423523DFA的状态图：盛威网（www.snwei.

13、com）专业的计算机学习网站9《编译原理》课后习题答案第四章bb013bab2b5baa4注意