资源描述：
《各章练习题发送版.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章复习重点：1.文法与语言的对应关系语言L(G)=L(G’)文法G文法G’{bn
2、n>0}B→bB
3、bB→Bb
4、b{bn
5、n≥0}P→bP
6、εP→Pb
7、ε{abn
8、n>0}S→DBD→aB→bB
9、bS→aBB→Bb
10、b{bna
11、n≥0}T→PDD→aP→bP
12、εT→PaP→Pb
13、ε{(ab)n
14、n>0}U→EU
15、EE→abU→Uab
16、ab{ambn
17、m>0,n>0}V→ABA→aA
18、aB→bB
19、bV→aV
20、aBB→bB
21、b{ambn
22、m≥0,n>0}W→ABA→aA
23、εB→bB
24、bW→aW
25、BB→b
26、B
27、b{anbn
28、n>0}X→aXb
29、ab{(akcd)nbn
30、k,n>0}X→DXH
31、DHD→AcdA→aA
32、aH→b{a2n+1bn
33、n>=0}Y→aaYb
34、aY→KYH
35、aK→aaH→b思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的“切割”？例：已知语言：L1={axb2xcy
36、x,y>=0}，给出此语言的文法，并证明此语言是上下文无关语言。提示：该题实际上要求为相应语言设计上下文无关文法。一个文法设计好后，严格来说应当证明此文法是否对应于该语言。解：G[S]：S→ABA→e
37、
38、aAbbB→e
39、cB推导过程：SÞAB+ÞaxAb2xB/*使用A→aAbbx次*/Þaxb2xB/*使用A→e一次*/Þaxb2xcxB/*使用B→cBx次*/Þaxb2xcx/*使用B→e一次*/举一反三：已知语言L2={axb2ycy
40、x,y>=0}，给出此语言的文法，并证明此语言是上下文无关语言。解：G[S]：S→ABA→e
41、aAB→e
42、bBcc练习：14：写出下列语言对应的文法(1).{anbnambm
43、n,m≥0}2.{1n0m0m0n
44、n,m≥0}3.{1n0m0m0n
45、n≥0,m>0}4
46、.{anbmck
47、n,m,k≥0}G1:S—>AAG2:S—>ABA—>aAb
48、εA—>aAb
49、εB—>aBb
50、εG:S—>1S0S—>AA—>0A1A—>εG:Sà1S0
51、ASà1S0
52、0A1Aà0A1
53、01Aà0A1
54、ε例：给出语言{akbmcn
55、k,m,n≥1}的正规文法（3型）。解：G:A→aA
56、aBB→bB
57、bCC→cC
58、c若不要求正规文法，则按例中上面分解的办法2.给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。1.令文法G［E］为：Z→bMbM→
59、a
60、(LL→Ma）①符号串b(Ma)b是否为该文法的一个句型，并证明。②若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。1）（5分）证明：S=>bMb=>b(Lb=>b(Ma)b所以，符号串b(Ma)b是该文法的一个句型。（2）（5分）短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)练习：（10分）已知文法G[T]：T→T*F
61、F；F→F↑P
62、P；P→(T)
63、i（1）用最右推导法证明β：T*P↑(T*F)是G[T]的一个句型；（2）画出β的语法树；（3）写出β的全部短语、直接短
64、语和句柄。(1)T=>T*F=>T*F↑P=>T*F↑(T)=>T*F↑(T*F)=>T*P↑(T*F)证毕。(2)如图（3）短语：T*P↑(T*F)；P↑(T*F)；(T*F)；T*F；P直接短语：T*F；P句柄：P3.证明一个文法是二义性文法。证明下述文法G［S］是二义的。（5分）S->iSeS
65、iS
66、i解：SSiSeSiSiSiSeS可见，句型iises有两种不同的语法树，所以G[S]是二义的。练习：证明下述文法G：S®aSbS
67、aS
68、d是二义性文法。解：一个文法，如果存在某个句子有不只一棵语法分
69、析树与之对应，那么称这个文法是二义性文法。SaSSabSdd句子aadbd有两棵语法树。如下图：dSSabSSad(1)(2)由此可知，S®aSbS
70、aS
71、d定义的文法是二义性文法。第四章:重点：1.NFAàDFA的确定化及DFA的最小化。2.试写出描述语言L的正规式，构造能识别该语言L等价的NFA，再确定化将下图所示的NFA确定化，再最小化。(2010年出过)X431baaeeaee2Y用子集法确定化如下表:编号IIaIbAA{X,1,2,4}B{1,2,3,4}C{1,2,4,Y}BB{1,2,3,
72、4}B{1,2,3,4}C{1,2,4,Y}CC{1,2,4,Y}B{1,2,3,4}C{1,2,4,Y}由于对于非终态的状态A和B来说，它们输入a、b的下一个状态都是一样的，故状态A和B可以合并，将合并后的状态重命名为A，而终态则重命名为B，则合并后的状态转换矩阵为：SabAABBAB由此可以得到最小化的DFA，如下图所示：ABab练习1：给出接受字母表å={a，b}，语言为以b开头，以aa结尾的字符串集合的正规表达式，并构造与之等价状态
