补充题：写出下列语言的上下文无关文法 (a){abab"1n,m≥0} G-((a.b).{S,A,B),S.I) T:S→AB:A→aAbl；B→aBbl9 (b){10101n,m20} G-({1,03,{S,A},S,四 正：S)1A0IAC:A→0A1I8 aca"loefa.b G-((ab.cJ,(S).S.I) I:s→aSa|bSb|8 (d)不以0开始的奇数集 G12.34567890-+.s.UEsm TS→+U-UU:U→AEE:E→113157I9:A→A0IA1IA2IA31.lA9I1I2I3LI9 11 (b)分析树 (1)a,a (a(aa))
补充题：写出下列语言的上下文无关文法 (a) a b a b | n,m 0 n n m m G=({a,b},{S,A,B},S,) : S→AB；A→aAb| ε ；B→aBb| ε (b) 1 0 1 0 | n,m 0 n m m n G=({1,0},{S,A},S,) : S→1A0|A| ε ；A→0A1| ε (c) c a b R | , G=({a,b,c},{S},S,) : S→aSa|bSb| ε (d) 不以 0 开始的奇数集 G=({1,2,3,4,5,6,7,8,9,0,-,+},{S,U,E},S,) : S→+U|-U|U；U→AE|E；E→1|3|5|7|9；A→A0| A1|A2|A3|.|A9|1|2|3|.|9 1.1 (b)分析树 (1)(a,a) S ( L ) L , S S a a (2) (a,(a,a)) S ( L ) L , S S ( L ) a L , S S a a
(3)(a.((a.a).(a.a)) (©)最左推导 (I)S(L)(LS)(S.S)(aS)(a.a) (2)S→) 短语：() 直接短语：（心） →LS) LSI(LS)) LS 3S.S) SISSISS) →(aS) ala.SI(a.S) a (a(L)) a|(la,)川(a(》 al(L) )(a(L.S)】 aL.S (L.S)I a(L.S)(a.(LS)) alLS 3(S.(S.S》 alSIS.SI(S,S)Ia(S,S)I(a.(S.S)) alS (a(aS)) alasl(as)la(as)l(a(as)) a (a(aa)) ala.al(a.a)|a(a.a|(a(a.a)) (3)S→→LS)→S,S)→(aS)→(aL》→(aL,S》→(a,(S,S》→a(.S →(a(L,S),S)→(a(S,S),S》→(a,(a,S),S)→(a(a,a,S)→(a,(aa()》 (a((a.a).(L.S))(a((a.a).(S.S)(a.((a.a).(a.S))(a.((a.a).(aa)) (d最右推导 (S(Sa(sa(aa) (2)S→→(LS)→L()→L(L,S)→(L(L,a)L(Sa》→L(a,a)→(,(aa →(a(aa) (3)S→L)→L,S)→L(L)→(L(L,S)→(LL(L))→L(LL,S)→(L(L).La)→ LL(S,a)→(L,L,(aa》→(L(S.(a,a》→L().(aa》→(LL,S.(aa》→ (L((La)(aa)))(L((Sa)(aa)))(L((aa)(aa)))(S.((aa)(aa)))(a((aa)(aa))) (e)生成语言 以a为基本元素构成的广义表 (a)最左推导 s→asbs→abSaSbS→abaSbS→ababS→abab
(3)(a,((a,a),(a,a))) S ( L ) L , S S ( L ) a L , S S ( L ) ( L ) L , S L , S S a S a a a (c)最左推导 (1) S➔(L)➔(L,S)➔(S,S)➔(a,S) ➔(a,a) (2) S ➔(L) 短语：(L) 直接短语：(L) ➔(L,S) L,S | (L,S)) L,S ➔(S,S) S | S,S | (S,S) S ➔(a,S) a | a,S | (a,S) a ➔(a,(L)) a | (L) | a,(L) | (a,(L)) a | (L) ➔(a,(L,S)) a | L,S | (L,S) | a,(L,S) | (a,(L,S)) a | L,S ➔(S,(S,S)) a | S | S,S | (S,S) | a,(S,S) | (a,(S,S)) a | S ➔(a,(a,S)) a | a,S | (a,S) | a,(a,S) | (a,(a,S)) a ➔(a,(a,a)) a | a,a | (a,a) | a,(a,a) | (a,(a,a)) a (3) S➔(L)➔(L,S)➔(S,S)➔(a,S) ➔(a,(L)) ➔(a,(L,S)) ➔(a,(S,S)) ➔(a,((L),S)) ➔ (a,((L,S),S)) ➔ (a,((S,S),S)) ➔ (a,((a,S),S)) ➔ (a,((a,a),S)) ➔ (a,((a,a),(L))) ➔(a,((a,a),(L,S))) ➔(a,((a,a),(S,S))) ➔(a,((a,a),(a,S))) ➔(a,((a,a),(a,a))) (d)最右推导 (1) S➔(L)➔(L,S)➔(L,a)➔(S,a) ➔(a,a) (2) S➔(L) ➔(L,S)➔(L,(L))➔(L,(L,S))➔ (L,(L,a)) ➔(L,(S,a)) ➔(L,(a,a)) ➔(S,(a,a)) ➔(a,(a,a)) (3) S➔(L)➔(L,S)➔(L,(L))➔ (L,(L,S)) ➔(L,(L,(L))) ➔(L,(L,(L,S))) ➔(L,(L),(L,a)))➔ (L,(L,(S,a))) ➔ (L,(L,(a,a))) ➔ (L,(S,(a,a))) ➔ (L,((L),(a,a))) ➔ (L,((L,S),(a,a))) ➔ (L,((L,a),(a,a))) ➔ (L,((S,a),(a,a)))➔ (L,((a,a),(a,a))) ➔(S,((a,a),(a,a))) ➔(a,((a,a),(a,a))) (e)生成语言 以 a 为基本元素构成的广义表 1.2 (a) 最左推导 S➔aSbS➔abSaSbS➔ abaSbS➔ ababS➔ abab
SaSbSabs abaSbs ababS abab 故文法是二义性的 ()最右推导 s→aSbSaSbaSbS aSbaSb→aSbab>abab s→aSbSaSb abSaSb abSab→abab (c)分析树 (2) b (d生成语言 由字母ab构成且ab个数相等的字符串组成的集合。 1.3b)分析树 false 补充题1：写出下列语言的三型文法 (a){a1n≥0} G({a,ss,Π m:S→asIe b){ab"1n,m21}
S➔aSbS➔abS➔ abaSbS➔ ababS➔ abab 故文法是二义性的。 (b) 最右推导 S➔aSbS➔aSbaSbS➔ aSbaSb ➔ aSbab➔ abab S➔aSbS➔aSb➔ abSaSb➔ abSab➔ abab (c) 分析树 (1) (2) S S a S b S a S b S a S b S b S a S (d)生成语言 由字母 a,b 构成且 a,b 个数相等的字符串组成的集合。 1.3(b)分析树 bexpr bterm bfactor not bfactor ( bexpr ) bexpr or bterm bterm bfactor bfactor false false 补充题 1：写出下列语言的三型文法 (a) a | n 0 n G=({a},{S}S,) : S→aS | ε (b) a b | n,m 1 n m
G=(fa.b).{S.B}.S.I) Π：S→aSJaB:B→blbB (@{abc1n,m,k≥1} G-((ab.cJ.{S.B.Cj.S.II) IS→aSJaB:B→bBlbC:C→clcC ()PASCAL的标识符 (.1.ab. LD aLDIbLD.zLDIALDIBLD.ZLDIOLD/1LDI.J9LD] (C)PASCAL整数 U→1Cl2Cl.l9cl C→0CUIe 补充题2：己知文法GS,其产生式如下：S→(S￡ (a)L(GSD是什么？ (b)对于(a)的结果，请给出证明 (a)解：L(GS)={()°1n20} b)证明： 1首先证明L(GSc{()°1n20} 对推导次数进行归纳 1):当推导次数为1时，使用产生式S→8，此时左括号与右括号个数为0 2):假设推导次数为n时(a)成立，即： 5((.S》=(.》 则推导次数为n+1次时，多使用一次产生式S→(S)即： s((.S.》=>(.S》=>(.》 推导次数为n+1次时(a)成立。 根据(1)(2)可得：L(GSc{（)”1n≥0} 2:其次证明{()°1n≥0}cL(GS 对n进行归纳 1)当n=0时，使用产生式S￡即可：
G=({a,b},{S,B},S,) : S→aS|aB；B→b|bB (c) a b c | n,m, k 1 n m k G=({a,b,c},{S,B,C},S,) : S→aS|aB；B→bB|bC；C→c|cC (d) PASCAL 的标识符 G=({0,1,.9,a,b,.z,A,B,.Z},{ID,LD},ID, ) : ID→aLD|bLD.zLD|ALD|BLD.|ZLD LD→ aLD|bLD.zLD|ALD|BLD.|ZLD|0LD|1LD|.|9LD| ε (e)PASCAL 整数 G=({0,1,.9,-,+},{S,U,C},S, ) : S→0|-U|+U|U U→1C|2C|.|9C| C→0C|U| ε 补充题 2：已知文法 G[S],其产生式如下：S→(S)| ε (a)L(G[S])是什么？ (b)对于(a)的结果，请给出证明 (a) 解：L(G[S])＝ ( ) | n 0 n n (b)证明： 1:首先证明 L(G[S]) ( ) | n 0 n n 对推导次数进行归纳 1):当推导次数为 1 时，使用产生式 S→ ε ，此时左括号与右括号个数为 0 2):假设推导次数为 n 时(a)成立,即: S (((. .))) −1 −1 + == n n S (((.))) −1 −1 == n n 则推导次数为 n+1 次时，多使用一次产生式 S→(S)即: S (((. .))) −1 −1 + == n n S (((. .))) n n == S (((.))) n n == 推导次数为 n+1 次时(a)成立。 根据(1)(2)可得：L(G[S]) ( ) | n 0 n n 2:其次证明 ( ) | n 0 n n L(G[S]) 对 n 进行归纳 1):当 n=0 时,使用产生式 S→ ε 即可；
2:假设当n减时，结论成立，即()广∈LGS,下面证n=k+1时结论成立。 由)∈L(GS,其推导过程如下： 5>((S.)》=>(》 当n=k+1时，推导过程如下 s三((S.》=>((.S.》=>(.》 故“")“∈L(G5S 根据(1)(2)可得：{()°1n≥0}cL(GS 根据1,2可知：L(GS={)°1n≥0}
2):假设当 n=k 时,结论成立，即 ( ) k k L(G[S])，下面证 n=k+1 时结论成立。 由 ( ) k k L(G[S])，其推导过程如下： S (((. .))) k k S + == (((.))) k k == 当 n=k+1 时，推导过程如下： S (((. .))) k k S + == (((. .))) +1 +1 == k k S (((.))) +1 +1 == k k 故 + + ( ) k 1 k 1 L(G[S]) 根据(1)(2)可得： ( ) | n 0 n n L(G[S]) 根据 1，2 可知：L(G[S])＝ ( ) | n 0 n n