资源描述：
《编译原理习题集.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章2.构造产生下列语言的文法（2）{anbmcp
2、n,m,p≥0}解：G(S)：S→aS
3、X,X→bX
4、Y,Y→cY
5、ε（3）{an#bn
6、n≥0}∪{cn#dn
7、n≥0}解：G(S)：S→X,S→Y,X→aXb
8、#,Y→cYd
9、#}（5）任何不是以0打头的所有奇整数所组成的集合解：G(S)：S→J
10、IBJ,B→0B
11、IB
12、ε,I→J
13、2
14、4
15、6
16、8,J→1
17、3
18、5
19、7
20、9}（6）（思考题）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S→0A
21、1B
22、ε，A→0S
23、1CB→0C
24、1SC→1A
25、0B3.描述语言特点（2）S→SSS→1A0A→1A0A→ε解：L(G)={1n10
26、n11n20n2…1nm0nm
27、n1,n2,…,nm≥0；且n1,n2,…nm不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。（5）S→aSSS→a解：L(G)={a(2n-1)
28、n≥1}可知：奇数个a5.(1)解：由于此文法包含以下规则：AA→ε，所以此文法是0型文法。7.解：(1)aacb是文法G[S]中的句子，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb不是文法G[S]中的句子aacbccb不能从S推导得到时，它仅是文法G[S]的一个句型的一部分，
29、而不是一个句子。11.解：最右推导:(1)S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为：短语直接短语句柄a1对A1√√b1a1对A2b2b1a1对A3c对S1√a2cb3对Bbbaacb对S2第三章3假设M:人W:载狐狸过河，G:载山羊过河，C:载白菜过河6根据文法知其产生的语言是L={ambnci
30、m,n,i≧1}可以构造如下的文法VN={S,A,B,C},VT={a,b,c}P={S→aA,A→aA,A→bB,B→bB,B→cC,C→cC,C→c}其状态转换图如下:7(1)其对应的右线性文法是:
31、A→0D,B→0A,B→1C,C→1
32、1F,C→1
33、0A,F→0
34、0E
35、1A,D→0B
36、1C,E→1C
37、0B(2)最短输入串011(3)任意接受的四个串：011,0110,0011,000011(4)任意以1打头的串.9．对于矩阵(iii)(1)状态转换图：(2)3型文法（正规文法）S→aA
38、a
39、bBA→bA
40、b
41、aC
42、aB→aB
43、bC
44、bC→aC
45、a
46、bC
47、b(3)用自然语言描述输入串的特征以a打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b所组成的任意串结尾或者以b打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b所组成的任意串结尾。12(1)确定化：ab[S]S[
48、S,A]A[S,A]A[S,A]A[A,B][A,B][B][A,B][B][B]-----------------------------------------------------以上为第一次作业最小化：º0º{S,A}{B,C}因为{S}b=φ{A}b={B}所以{S,A}=>{S}{A}因为{C}b=φ{B}b={B}所以{B,C}=>{B}{C}º1º{S}{A}{B}{C}原DFA已为最小DFA。10（1）G1的状态转换图：或(2)G1等价的左线性文法G1’[F]：F→Dd
49、Bb,D→C,B→S
50、ε
51、Ab
52、Db,A→Sa
53、a,C→Bc,S→Eb,E→Aa或G1’[F]：F
54、→Dd
55、Bb,D→C,B→S
56、ε
57、Ab
58、Db,A→Sa
59、a,C→Bc,S→Aab21求出描述习题3-12中图（2）（3）所给出有限自动机所识别语言的正规式（2）a(ba)*b或(ab)*ab（3）a（b
60、aa)*a-----------------------------------------------------以上为第二次作业22(1)((0*
61、1)(1*0))*0ε1ε10εASBCNFA:确定化： ∑Q00ASBAA010111[S,A,B]S[S,A,B,C]A[B]B[S,A,B,C]A[S,A,B,C]A[B]B[B]B[S,A,B,C]A[B]B第四章1(2)将间接左
62、递归转换成直接左递归，将A->SAA->a代入S->AS由原文法得S->SAS
63、aS
64、b消除左递归：S->aSS’
65、bS’S’->ASS’
66、ε4又ε属于First(S)，First(S)ÇFollow(S)=Æ又ε属于First(A)，First(A)ÇFollow(A)=Æ又ε属于First(B)，First(A)ÇFollow(A)=Æ所以此文法为LL(1)文法。8.（1）(a)消除左递归：S->Sb
67、Ab
68、b=>S->AbS’
