編譯原理第二章 習題與答案(修改后)

1、第2章習題習題21設有字母表A1=abc…z，A2=01…9，試回答下列問題：(1)字母表A1上長度為2的符號串有多少個？(2)集合A1A2含有多少個元素？(3)列出集合A1(A1∪A2)中的全部長度不大于3的符號串。22試分別構(gòu)造產(chǎn)生下列語言的文法：（1）anbn|n≥0；（2）anbmcp|nmp≥0；（3）an#bn|n≥0∪cn#dn|n≥0；（4）w#wr#|w∈01wr是w的逆序排列；（5）任何不是以0打頭的所有奇整數(shù)所組成

2、的集合；（6）所有由偶數(shù)個0和偶數(shù)個1所組成的符號串的集合。23試描述由下列文法所產(chǎn)生的語言的特點：（1）S→10S0S→aAA→bAA→a（2）S→SSS→1A0A→1A0A→ε（3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε（4）S→aSSS→a24試證明文法S→AB|DCA→aA|aB→bBc|bcC→cC|cD→aDb|ab為二義性文法。25對于下列的文法S→AB|cA→bA|aB→aSb|c試給出句子bbaa

3、cb的最右推導，并指出各步直接推導所得句型的句柄；指出句子的全部短語。(4)G(S)=(SWR01#S→W#W→0W0|1W1|#S)(5)G(S)=(SABIJ0123456789S→J|IBJB→0B|IB|εI→J|2|4|6|8J→1|3|5|7|9S)(6)對應文法為S→0A|1B|ε，A→0S|1C，B→0C|1S，C→1A|0B23解：(1)本文法構(gòu)成的語言集為：L(G)=(10)nabma0n|nm≥0。(2)L(G)=

4、1n0n|n≥0，該語言特點是：產(chǎn)生的句子中，0、1個數(shù)相同，并且若干相接的1后必然緊接數(shù)量相同的連續(xù)的0。(3)本文法構(gòu)成的語言集為：L(G)=1p1n0n|p≥1n≥0∪1n0n0q|q≥1n≥0，特點是具有1p1n0n或1n0n0q形式，進一步，可知其具有形式1n0m|nm≥0且nm0。(4)由L(G)=a2n1|n≥1可知，該語言特點是：產(chǎn)生的句子是奇數(shù)個a。24證明：因為存在句子：abc，它對應兩個最右推導：S?AB?Abc?