第三章复习重点：1.文法与语言的对应关系
语言L(G)=L(G’) 文法G {bn | n>0} B→bB | b n{b | n≥0} P→bP |ε S→DB n{ab | n>0} D→a B→bB | b T→PD n{ba | n≥0} D→a P→bP |ε U→EU | E {(ab)n | n>0} E→ab V→AB mn{ab|m>0,n>0} A→aA | a B→bB | b W→AB mn{ab|m≥0,n>0} A→aA |ε B→bB | b nn {ab| n>0} X→aXb | ab {(akcd) nbn | k,n>0} {a2n+1bn| n>=0} Y→aaYb |a 文法G’ B→Bb | b P→Pb |ε S→aB B→Bb | b T→Pa P→Pb |ε U→Uab | ab V→aV | aB B→bB | b W→aW | B B→bB | b X→DXH | DH D→Acd A→aA |a H→b Y→KYH | a K→aa H→b
思路要点：注意结构拆分
技巧：如何将表示语言的通用字符串形式作适当的“切割”？
例：已知语言：L1 = {abc | x, y >= 0}，给出此语言的文法，并证明此语言是上
x2xy
下文无关语言。
提示：该题实际上要求为相应语言设计上下文无关文法。
一个文法设计好后，严格来说应当证明此文法是否对应于该语言。
解：G[S]： S → AB A → ? | aAbb B → ? | cB
推导过程：
S ? AB +? axAb2xB /*使用A → aAbb x次*/ ? axb2xB /*使用A → ? 一次*/ ? axb2xcxB /*使用B → cB x次*/
? axb2xcx /*使用B →? 一次*/
举一反三：已知语言L2 = {axb2ycy | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。
解：G[S]： S → AB A → ? | aA B → ? | bBcc
练习：14：写出下列语言对应的文法 (1).{anbnambm|n,m≥0}
2. {1n0m0m0n|n,m≥0} 3. {1n0m0m0n|n≥0,m>0} 4. { anbmck|n,m,k≥0}
G1: S—>AA G2: S—>AB
A—>aAb|ε A—>aAb|ε B—>aBb|ε G: S—>1S0 S—>A A—>0A1 A—>ε
G: S?1S0|A S?1S0|0A1 A?0A1|01 A?0A1|ε
2. 给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。
1. 令文法G［E］为：
Z→bMb M→a|(L L→Ma）
① 符号串b(Ma)b是否为该文法的一个句型，并证明。
② 若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。 1）（5分）证明：S=> bMb=>b(Lb=>b(Ma)b
所以，符号串b(Ma)b是该文法的一个句型。 （2）（5分）短语: Ma)， (Ma)， b(Ma)b
直接短语: Ma