编译原理（第2版）课后习题答案详解 (5)

x0=(aaa)0=ε | x0|=0

xx=aaaaaa |xx|=6

x5=aaaaaaaaaaaaaaa | x5|=15

A+ =A1 ∪ A2 ∪ ?. ∪ A n ∪?={a,aa,aaa,aaaa,aaaaa?}

A* = A0 ∪A1 ∪ A2 ∪ ?. ∪ A n ∪?={ε,a,aa,aaa,aaaa,aaaaa?}

问题 11：

令Σ={a，b，c}，又令 x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz， （xy）3

答案：

xy=abcb |xy|=4

xyz=abcbaab |xyz|=7

(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12

问题 12：

已知文法 G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文 法描述的只含有四个符号的句子。

答案：

Z=>U0=>Z10=>U010=>1010

Z=>U0=>Z10=>V110=>0110

Z=>V1=>Z00=>U000=>1000

Z=>V1=>Z00=>V100=>0100

问题 13：

已知文法 G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。

答案：

A∷=aA︱ε描述的语言: {an|n>=0}

B∷=bBc︱bc描述的语言:{,bncn|n>=1}

L(G[S])={anbmcm|n>=0,m>=1}

问题 14：

已知文法E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开

始符号、终结符号集合VT、非终结符号集合VN。

答案：

开始符号：E

VT={+, - , * , / ,（ , ）, i}

VN={E , F , T}

问题 15：

设有文法 G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？

答案：

根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。

问题 16：

写一文法，使其语言是奇正整数集合。

答案：

A::=1|3|5|7|9|NA

N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|

N::=0|1|2|3|4|5|6|7|8|9 S S * S S + S a a a S S + S a S * S a a

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新医药卫生编译原理（第2版）课后习题答案详解 (5)全文阅读和word下载服务。