第2章习题2-1设有字母表A1={a,b,c,…,z}，A2={0,1,…,9}，试回答下列问题：(1)字母表A1上长度为2的符号串有多少个？(2)集合A1A2含有多少个元素？(3)列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。2-2试分别构造产生下列语言的文法：（1）{anbn|n≥0}；（2）{anbmcp|n,m,p≥0}；（3）{an#bn|n≥0}∪{cn#dn|n≥0}；（4）{w#wr#|w∈{0,1}*,wr是w的逆序排列}；（5）任何不是以0打头的所有奇整数所组成的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。2-3试描述由下列文法所产生的语言的特点：（1）S→10S0S→aAA→bAA→a（2）S→SSS→1A0A→1A0A→ε（3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε（4）S→aSSS→a2-4试证明文法S→AB|DCA→aA|aB→bBc|bcC→cC|cD→aDb|ab为二义性文法。2-5对于下列的文法S→AB|cA→bA|aB→aSb|c试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。2-6化简下列各个文法(1)S→aABS|bCACdA→bAB|cSA|cCCB→bAB|cSBC→cS|c(2)S→aAB|EA→dDA|eB→bE|fC→cAB|dSD|aD→eAE→fA|g(3)S→ac|bAA→cBCB→SAC→bC|d2-7消除下列文法中的ε-产生式(1)S→aAS|bA→cS|ε(2)S→aAAA→bAc|dAe|ε2-8消除下列文法中的无用产生式和单产生式(1)S→aB|BCA→aA|c|aDbB→DB|CC→bD→B(2)S→SA|SB|AA→B|(S)|()B→[S]|[](3)E→E+T|TT→T*F|FF→P↑F|PP→(E)|i第2章习题答2-1答：(1)26*26=676(2)26*10=260(3){a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共有26+26*36+26*36*36=34658个2-2解：(1)对应文法为G(S)=({S},{a,b},{S→ε|aSb},S)(2)对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)(3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb|#,Y→cYd|#},S)(4)G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0|1W1|#},S)(5)G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8,J→1|3|5|7|9},S)(6)对应文法为S→0A|1B|ε，A→0S|1C，B→0C|1S，C→1A|0B2-3解：(1)本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。(2)L(G)={1n0n|n≥0}+，该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0。(3)本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n或1n0n0q形式，进一步，可知其具有形式{1n0m|n,m≥0,且n+m>0}。(4)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。2-4证明：因为存在句子：abc，它对应两个最右推导：SABAbcabcSDCDcabc所以，本文法具有二义性。2-5解：句子bbaacb的最右推导为：SABAaSbAacbbAacbbbAacbbbaacb上面推导中，下划线部分为当前句型的句柄。与句子bbaacb相应的语法树为：全部的短语为：第一个a（a(1)）是句子bbaacb相对于非终结符A(A(1))(产生式A→a）的短语（直接短语）；b(1)a(1)是句子bbaacb相对于非终结符A(2)的短语；b(2)b(1)a(1)是句子bbaacb相对于非终结符A(3)的短语；c是句子bbaacb相对于非终结符S(1)（产生式S→c）的短语（直接短语）；a(2)cb(3)是句子bbaacb相对于非终结符B的短语；b(2)b(1)a(1)a(2)cb(3)是句子bbaacb相对于非终结符S(2)的短语；注：符号的上标是为了描述方便加上去的。2-6解：(1)