【正文】 L(G)＝ L(M)，則稱 G和 M是 等價(jià) 的。 FA M，都存在一個(gè)右線性正規(guī)文法 GR和左線性正規(guī)文法 GL，使得 L(M)＝ L(GR)＝ L(GL)。 (1) 設(shè)右線性正規(guī)文法 G=VT, VN, S, P 。 令 M=VN∪ {f}, VT, ?, S, {f}，其中狀態(tài)轉(zhuǎn)換函數(shù) ?由以下規(guī)則定義： 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 (a) 若對(duì)某個(gè) A?VN及 a?VT∪ {?}， P中有產(chǎn)生式 A→a ，則令 ?(A,a)=f (b) 對(duì)任意的 A?VN及 a?VT∪ {?}，設(shè) P中左端為 A，右端第一符號(hào)為 a的所有產(chǎn)生式為： A→aA 1|…|aA k （不包括 A→a ）， 則令 ?(A,a)={A1,…,A k}。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 對(duì)于右線性正規(guī)文法 G，在 S w的最左推導(dǎo)過(guò)程中 : ? 利用 A?aB一次就相當(dāng)于在 M中從狀態(tài) A經(jīng)過(guò)標(biāo)記為 a的箭弧到達(dá)狀態(tài) B（包括 a=?的情形） 。 綜上，在正規(guī)文法 G中， S w的充要條件是：在 M中，從狀態(tài) S到狀態(tài) f有一條通路，其上所有箭弧的標(biāo)記符號(hào)依次連接起來(lái)恰好等于 w，這就是說(shuō)， w?L(G)當(dāng)且僅當(dāng)w?L(M)，故 L(G)＝ L(M)。將VN中的每一符號(hào)視為狀態(tài)符號(hào)，并增加一個(gè)初始狀態(tài)符號(hào) q0， q0?VN。 與 (1)類似，可以證明 L(G)＝ L(M)。 ? 顯然 L(M) = L(GR)。 設(shè) DFA M=S, ?, ?, s0, F (1) 若 s0?F，我們令 GR=?, S, s0, P，其中 P是由以下規(guī)則定義的產(chǎn)生式集合： 對(duì)任何 a??及 A,B?S，若有 ?(A,a)=B，則： (a) 當(dāng) B?F時(shí)，令 A→aB ， (b) 當(dāng) B?F時(shí)，令 A→a|aB 。若 s0 w，則存在一個(gè)最左推導(dǎo)： s0?a1A1?a1a2A2?… ?a1…a iAi ?a1…a i+1Ai+1?… ?a1…a k 因而，在 M中有一條從 s0出發(fā)依次經(jīng)過(guò) A1， … ，Ak1到達(dá)終態(tài)的通路，該通路上所有箭弧的標(biāo)記依次為 a1,…,a k。所以，w?L(GR)當(dāng)且僅當(dāng) w?L(M)。但 ?不屬于上面構(gòu)造的 GR所產(chǎn)生的語(yǔ)言 L(GR)。所以，我們?cè)谏鲜?GR中添加新的非終結(jié)符號(hào) s0?， (s0??S)和產(chǎn)生式 s0??s0|?，并用 s0?代替 s0作開始符號(hào)。 (2) 類似于 (1)，從 DFA M出發(fā)可構(gòu)造左線性正規(guī)文法 GL，使得 L(GL)=L(M)。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? L(M) = 0(10)* ? GR = {0, 1}, {A, B, C, D}, A, P，其中 P由下列產(chǎn)生式組成： A→0 | 0B | 1D B→0D | 1C C→0 | 0B | 1D D→0D | 1D L(GR) = L(M) = 0(10)* 例 設(shè) DFA M = {A, B, C, D}, {0, 1}, ?, A, {B}。 A B C D 1 0 0,1 1 1 0 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 從 NFA M出發(fā)構(gòu)造左線性正規(guī)文法 GL = {0, 1}, {B, C, D, f}, f, P?，其中 P?由下列產(chǎn)生式組成： f→0 | C0 C→B1 B→0 | C0 D→1 | C1 | D0 | D1 | B0 易證 L(GL) = L(M)。 M的狀態(tài)轉(zhuǎn)換圖如圖 (a)所示。 2. 對(duì)任何正規(guī)式 r，都存在一個(gè) FA M，使得 L(M)=L(r)。 (對(duì)一類輸入符號(hào) ) 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 證明： 1 對(duì) ?上任一 NFA M，構(gòu)造一個(gè) ?上的正規(guī)式 r，使得 L(r)=L(M)。 ?然后，反復(fù)使用下面的一條規(guī)則，逐步消去的所有結(jié)點(diǎn)，直到只剩下 X和 Y為止； 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 代之為 i j r1 r2 k i k r1r2 代之為 i j r1|r2 i j r2 r1 代之為 i k r1r2*r2 i j r1 r3 k r2 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 1 2 3 5 4 U1 V1 U2 V2 W2 W1 1 2 5 4 V1(U1|U2)*W1 V1(U1|U2)*W2 V2(U1|U2)*W2 V2(U1|U2)*W1 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 最后， X到 Y的弧上標(biāo)記的正規(guī)式即為所構(gòu)造的正規(guī)式 r ? 顯然 L(r)=L(M)=L(M’) 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 證明 2: 對(duì)于 ?上的正規(guī)式 r，構(gòu)造一個(gè)NFA M，使 L(M)=L(r)，并且 M只有一個(gè)終態(tài)，而且沒有從該終態(tài)出發(fā)的箭弧。 (1) 若 r具有零個(gè)運(yùn)算符，則 r=?或 r=?或 r=a，其中 a??。 q0 q0 qf a q0 qf 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 (2) 假設(shè)結(jié)論對(duì)于少于 k(k?1)個(gè)運(yùn)算符的正規(guī)式成立。從而，由歸納假設(shè)，對(duì) ri存在 Mi=Si, ?i, ?i, qi, {fi}，使得 L(Mi)=L(ri)，并且 Mi沒有從終態(tài)出發(fā)的箭?。?i=1,2）。 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 令 M=S1∪ S2∪ {q0,f0}, ?1∪ ?2, ?, q0, {f0}，其中 ?定義如下： (a) ?(q0, ?)={q1,q2} (b) ?(q,a)= ?1(q,a), 當(dāng) q?S1{f1}, a??1∪ {?} (c) ?(q,a)= ?2(q,a), 當(dāng) q?S2{f2}, a??2∪ {?} (d) ?(f1,?)=?(f2,?)={f0}。 L(M)=L(M1)∪ L(M2) =L(r1)∪ L(r2)=L(r) ? q0 f0 M1 q1 f1 M2 q2 f2 ? ? ? 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 情形 2： r=r1r2, 設(shè) Mi同情形 1(i=1,2)。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。設(shè) M1同情形 1。 M的狀態(tài)轉(zhuǎn)換如右圖所示。 ? M1 q1 f1 q0 f0 ? ? ? 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 1) 構(gòu)造 ?上的 NFA M? 使得 L(V)=L(M?) 首先，把 V表示成 X Y V 上述證明過(guò)程實(shí)質(zhì)上是一個(gè)將正規(guī)表達(dá)式轉(zhuǎn)換為有限自動(dòng)機(jī)的算法。 ? 兩個(gè)狀態(tài)不等價(jià)，則稱它們是 可區(qū)別 的。最后，讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。 ?假定到某個(gè)時(shí)候， ?已含 m個(gè)子集，記為?={I(1)， I(2)， ? ， I(m)}，檢查 ?中的每個(gè)子集看是否能進(jìn)一步劃分 : ?對(duì)某個(gè) I(i)，令 I(i)={s1,s2, ? ,sk}，若存在一個(gè)輸入字符 a使得 Ia(i) 不會(huì)包含在現(xiàn)行 ?的某個(gè)子集 I(j)中，則至少應(yīng)把 I(i)分為兩個(gè)部分。則將分成兩半，使得一半含有 s1: I(i1)={s|s?I(i)且 s經(jīng) a弧到達(dá) t, 且 t與 t1屬于現(xiàn)行 ?中的同一子集 } 另一半含有 s2: I(i2)=I(i)I(i1) 國(guó)防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 一般地，對(duì)某個(gè) a和 I(i)，若 Ia(i) 落入現(xiàn)行 ?中 N個(gè)不同子集，則應(yīng)把 I(i)劃分成 N個(gè)不相交的組，使得每個(gè)組 J的 Ja都落入的 ?同一子集。 ? 重復(fù)上述過(guò)程，直到 ?所含子集數(shù)不再增長(zhǎng)。 ? 若 I含有原來(lái)的初態(tài)，則其代表為新的初態(tài)，若 I含有原來(lái)的終態(tài)，則其代表為新的終態(tài)