【正文】 0 1 0 1 1 1 1 (a,b): ab 0 1 be ? (a,c): ac 0 1 ba (a,d): ad 0 1 bf bd 0 1 cd 0 1 ef 0 1 bc 0 1 (b,c): (b,d): (c,d): (e,f): ea ef fe af dd fe 得： b?d, e?f , a?a ,c?c 于是 K/?{{a},{b,d},{c},{e,f}}， 五 ． 構造簡化的有限自動機 定理 給定 DFA M＝ (K,∑,δ,q0,F)， 可根據(jù)引理 21中 的算法構造出除去不可達狀態(tài)的具有更少狀態(tài)的 DFA M’， 使得 T(M’)=T(M)。 解 ：有兩種方法。 (2) S?A 得 : A? ε (3) 由 A?0B 得 : B?A0 由 A?1C 得 : C?A1 由 B?0A 得 :A ?B0 由 B?1C 得 : C?B1 由 C?0B 得 :B?C0 由 C?1B 得 : B?C1 (4)由 A?1 得 : S?A1 由 A?ε 得 : S?A 由 B?0 得 : S?B0 由 B?1 得 : S?B1 整理得左線性文法 G: S?A1|B0 |B1|A A ?B0| ε B?A0| C0 | C1 C?A1|B1 表面上看與方法 1得結果略有些不同 S?A|C| ε A?B0 B?A0|C0|C1|0 C?A1|B1|1 10． 首先構造一個右線性文法 G， 使得 L(G)={ai bj|i,j≥0}∪ {ck|k≥0} 再構造一個有限自動機 M， 使得 T(M)=L(G)。 證明 : (1) 假設 L是正規(guī)集。 (4)令 u=an1, v=an2, w=an3, 于是 |uv|=n1+n2≤n, |v|=n2≥1, n1+n2+n3=m , z=uvw=an1+n2+n3 = a m, uviw=an1+in2+n3 =a(n1 +n2+n3)+(i1)n2 =am+(i1)n2 取 i=m+1,則 uvm+1w=am+(m+11)n2 =am+mn2 =am(1+n2) 由于 n2≥1， 所以 1+ n2 ≥2, 而 m≥2, 所以 m(1+n2)不是素 數(shù)，故 uvm+1w?L， 產生矛盾。 利用兩個引理，去掉無用符號。 1） 置初值：Ｖ Ｎ ’ :={S}， Ｖ Ｔ ’ :=Φ。 最后得到Ｖ Ｎ ’ 、Ｖ Ｔ ’ 。 下面對 G’’去掉單一產生式 : 對任何 A,B∈ Ｖ Ｎ ，如果有 A?*B， 且 B?α1|α2|…|αn 是 P’’中 B的所有非單一產生式，則把 所有 A?α1|α2|…|αn 加到 P’’’ 中。 顯然有 A、 C、 B和 S。 于是最后得： S→ABC|BC|AC|AB|C|B|A, A→BB|B, B→CC|C|a, C→AA|A|b, 3．給定 CFG G=({S,A },{0,1}, P, S )， 其中， P： S→AA ∣ 0, A→SS ∣ 1, 將 G寫成 GNF形式 。 棧內符號： A， B， R (R是開始時棧內符號 )。 如果 w中 a,b的個數(shù)相等 ， 則 M讀完 w后 ， 棧頂應該是 R， 此時 M進入終止狀態(tài) q2 。 解 :(1)先簡化 G， 因為 G中無 ε產生式和單一產生式，所 以只去掉無用符號： 對 G應用引理 ，執(zhí)行上述算法， 得到的結果如下表所示： 得 G’=({S,A},{a,b,c},P’,S) P’： S→aA A→bSa | Ab | b ， 循環(huán)次數(shù) i 初值 1 2 3 OLDＶ Ｎ NEWＶ Ｎ {A, S} {A} Φ {A} {A,S} {A, S} P’： S→aA A→bSa | Ab | b ， 再對 G’應用引理 ，執(zhí)行算法的結果如下表所示： 得 G’’=({S,A},{a,b},P’’,S) P’’: S→aA A→bSa | Ab | b ， (2)將 G’’變成 GNF形式 先變成： S→aA, A→bSD | Ab | b , D ?a ， 處理左遞歸 A→Ab | bSD | b , 變成： A→bSD | b | bSDZ|bZ, Z ?b |bZ 最后得： S→aA ， A→bSD|b|bSDZ|bZ, Z ?b|bZ， D ?a 循環(huán)次數(shù) i 初值 1 2 3 Ｖ Ｎ ’’ {S} {S,A} {S,A} Ｖ T’’ Φ {a} { a,b } S→aA ， A→bSD| b| bSDZ| bZ, Z ?b | bz， D ?a ， (3)根據(jù)上述文法，構造 PDAM’使得 N(M’)=L(G) M’=({q},{a,b},{S,A,D,Z},δ,q,S,Φ) δ:由 S→aA 得： δ(q,a,S)={(q,A)} 由 A→bSD| b| bSDZ| bZ 得： δ(q,b,A)={(q,SD),(q,ε),(q,SDZ),(q,Z)} 由 Z?b|bz得： δ(q,b,Z)={(q,ε),(q,Z)} 由 D ?a 得： δ(q,a,D)={(q,ε)} (4)根據(jù) M’變成 M,使得 T(M)=N(M’). M=({q0,q,q1},{a,b},{S,A,D,Z,E},δ’,q0,E,{q1}) δ’: δ’(q0,ε,E)={(q,SE)} δ’(q,a,S)={(q,A)} δ’(q,b,A)={(q,SD),(q,ε),(q,SDZ),(q,Z)} δ’(q,b,Z)={(q,ε),(q,Z)} δ’(q,a,D)={(q,ε)} δ’(q,ε,E)= {(q1,ε)} 6． 給定 PDA M=({q0,q1},{0,1},{Z0 ,X },δ, q0,Φ)， 其中 δ如下： ⑴ δ(q0,1, Z0)={(q0, XZ0)} ⑵ δ(q0,1,X)={(q0, XX) } ⑶ δ(q0,0, X)={(q1, X)} ⑷ δ(q0,ε, Z0)={(q0,ε) } ⑸ δ(q1,1, X)={( q1,ε)} ⑹ δ(q1,0, Z0)={(q0, Z0) } 求一個 CFG G 使得 L(G)=N(M). 解 ： 令 M=(K,Σ,Γ,δ,q0,Z0,Φ)， N(M)=L。 由 ⑸ δ(q0,ε,Z0)={(q0,ε)}得 15） [q0,Z0,q0]?ε 由 ⑹ δ(q1,1,X)={(q1,ε)}得 16） [q1,X,q1]?1 下面對這些產生式進行整理。 (3)取 z＝ am， m≥n 且 m是個素數(shù)。 謝 謝！ 放映結束 感謝各位觀看！ 讓我們共同進步