第三章复习重点：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. {1n0m1m0n|n,m≥0} 3. {1n0m1m0n|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) 句柄: Ma) 练习： （10分）已知文法G[T]： T→T*F | F ；F→F↑P | P ； P→(T) | i （1）用最右推导法证明β：T*P↑(T*F) 是G[T]的一个句型； （2）画出β的语法树； （3）写出β的全部短语、直接短语和句柄。 (1) T=>T*F=>T*F↑P=>T*F↑(T)=> T*F↑(T*F) =>T*P↑(T*F) 证毕。 (2) 如图 T T * F P F ↑ ( P T ) T 第3题 语法树 * F （3）短语：T*P↑(T*F) ；P↑(T*F) ；(T*F) ；T*F ；P 直接短语：T*F ；P
句柄： P
3. 证明一个文法是二义性文法。
证明下述文法G［S］是二义的。 （5分） S->iSeS|iS|i
解：
S S
i S e S i S
i S i S e S
可见，句型iises有两种不同的语法树，所以G[S]是二义的。 练习：证明下述文法G： S?aSbS|aS|d 是二义性文法。 解：
一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。
句子aadbd有两棵语法树。如下图：
S S
a S S a S b
S a S b a d S
d d
d (1) (2)
由此可知，S?aSbS|aS|d定义的文法是二义性文法。 第四章: 重点：1. NFA?DFA的确定化及DFA的最小化。 2. 试写出描述语言L的正规式，构造能识别该语言L等价的NFA，再确定化 将下图所示的NFA确定化，再最小化。(2010年出过) 3 a X a 1 ? ? ? ? b 2 Y 4 a b 用子集法确定化如下表: 编号 A B C I A{X,1,2,4} B{1,2,3,4} Ia Ib B{1,2,3,4} C{1,2,4,Y} B {1,2,3,4} C{1,2,4,Y} C{1,2,4,Y} B {1,2,3,4} C{1,2,4,Y} 由于对于非终态的状态A和B来说，它们输入a、b的下一个状态都是一样的，故状态A和B可以合并，将合并后的状态重命名为A，而终态则重命名为B，则合并后的状态转换矩阵为： S A B 由此可以得到最小化的DFA，如下图所示： a A B b a A A b B B
练习1：给出接受字母表?={a，b}，语言为以b开头，以aa结尾的字符串集合的正规表达式，并构造与之等价状态的DFA。（2010年出过） 答：依题意，以b开头，以aa结尾的字符串集合的正规表达式可写为： b(a|b)*aa 画NFA，如下图所示 a X b 1 a 2 a Y I Ia Ib 0 b 用子集法确定化如下表 {X}A - {1}B {1} B {1,2}C {1} B {1,2}C {1,2,Y}D {1} B {1,2,Y}D {1,2,Y}D. {1} B b A b B a b a C a D （10分）将下图的NFA确定化为DFA。（2011年重修卷A出过）
b
答：用子集法确定化如下表 用子集法对所给图的确定化 I {X,1,2} {1,2}.. {1,2,3} {1,2,Y} 确定化后如下图 Ia {1,2}.. {1,2}.. {1,2,Y} {1,2}.. Ib {1,2,3} {1,2,3} {1,2,3} {1,2,3} 状态 X 1 2 3
第五章重点：1.LL(1)的判别 要点：（1）计算First\\Follow\\Select集，然后判断是否是LL(1)文法。 （2）如果是LL(1)文法，则构造预测分析表。 （消除左递归和左公共因子也要了解） 例：（10分）已给文法 G[S] ： S → PS' S' → aPS'| fS' |? P → qP'
P' → bP |?
（1）该文法是否是LL（1）文法，并说明理由。 （2）给出该文法的预测分析表。 答：（10 分）
（1）Select（S → PS'）=first(P)={q} Select(S’→ aPS')={a} Select(S’→ fS')={f}
Select(S' →?)=follow(S’)=follow(S)={#} Select(P→ qP')={q}
Select(P' → bP)={b} Select（ P' →?）=follow(P’)
=follow(P)={first(S’)-{ ?}}?follow(S)={a,f}?{#}={a,f,#} Select(S’→ aPS')? Select(S’→ fS') ? Select(S' →?)=? Select(P' → bP) ? Select（ P' →?）=? 所以文法是LL（1）文法。 （7分）