第3章詞法分析與有限自動(dòng)機(jī)

1、本章目標(biāo)v 解釋詞法分析器的工作原理及設(shè)計(jì)實(shí)現(xiàn)v 介紹單詞的描述工具：正規(guī)文法和正規(guī)式v 定義DFA和NFA的概念v 介紹“正規(guī)式NFADFA最小化DFA”的轉(zhuǎn)換方法v 介紹有限自動(dòng)機(jī)、正規(guī)文法和正規(guī)式的等價(jià)性v 介紹詞法分析器的自動(dòng)構(gòu)造工具-LEX的原理與實(shí)現(xiàn)教學(xué)內(nèi)容3.1 3.1 詞法分析器的設(shè)計(jì)思想詞法分析器的設(shè)計(jì)思想3.2 3.2 詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)3.3 3.3 單詞的描述工具單詞的描述工具3.4 3.4 有限自動(dòng)機(jī)有限自動(dòng)機(jī)3.5 3.5 正規(guī)式、正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性正規(guī)式、正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性3.6 3.6 詞法分析器的自動(dòng)構(gòu)造工具詞法分析器的自動(dòng)構(gòu)

2、造工具LEXLEX3.7 3.7 本章小結(jié)本章小結(jié)3.1 詞法分析器的設(shè)計(jì)思想詞法分析器的任務(wù)和輸出形式詞法分析器的任務(wù)和輸出形式 1將詞法分析工作分離的考慮將詞法分析工作分離的考慮 21、詞法分析器的任務(wù)和輸出形式（1）詞法分析器的任務(wù) 自左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，按語言的構(gòu)詞規(guī)則識(shí)別出一個(gè)個(gè)單詞，把作為字符串的源程序改造為單詞符號(hào)串的中間程序。字符串流字符串流單詞流單詞流源語言程序源語言程序單詞符號(hào)單詞符號(hào)1、詞法分析器的任務(wù)和輸出形式（2）單詞符號(hào)單詞符號(hào)是程序設(shè)計(jì)語言的基本語法單位和最小語義單位。（3）單詞符號(hào)的種類 ：標(biāo)記常量、變量、函數(shù)等的名字，如fun、i ：具有固定意義

3、的標(biāo)識(shí)符，如if、while、for ：各種類型的常數(shù)，如實(shí)型0.618，布爾型TRUE ：如+、-、*、/、=、 、 = 、= ：如，、；、（、），單詞符號(hào)1、詞法分析器的任務(wù)和輸出形式（4）單詞符號(hào)的輸出形式 二元式： （ 單詞種別， 單詞符號(hào)的屬性值） ，它是語，它是語法分析所需要的信息。一法分析所需要的信息。一個(gè)語言的單詞符號(hào)如何劃個(gè)語言的單詞符號(hào)如何劃分種類、分為幾類、如何分種類、分為幾類、如何編碼都屬于技術(shù)性問題，編碼都屬于技術(shù)性問題，主要取決于處理上的方便。主要取決于處理上的方便。，這樣可最大限度，這樣可最大限度地把各個(gè)單詞區(qū)別開來。地把各個(gè)單詞區(qū)別開來。用來區(qū)分該類單詞中的哪一

4、用來區(qū)分該類單詞中的哪一個(gè)單詞，它是單詞本身的機(jī)個(gè)單詞，它是單詞本身的機(jī)內(nèi)編碼。內(nèi)編碼。例如，對(duì)于某個(gè)標(biāo)識(shí)符，例如，對(duì)于某個(gè)標(biāo)識(shí)符，常將存放它的有關(guān)信息的符常將存放它的有關(guān)信息的符號(hào)表項(xiàng)的指針作為其屬性值；號(hào)表項(xiàng)的指針作為其屬性值；而對(duì)于某個(gè)常數(shù)，則是將存而對(duì)于某個(gè)常數(shù)，則是將存放它的常數(shù)表項(xiàng)的指針作為放它的常數(shù)表項(xiàng)的指針作為其屬性值。其屬性值。1、詞法分析器的任務(wù)和輸出形式（4）單詞符號(hào)的輸出形式常用單詞種別編碼方案 標(biāo)識(shí)符：一種 關(guān)鍵字：全體視為一種或一字一種 常 數(shù)：按類型分種，如整數(shù)、實(shí)數(shù)、布爾型 運(yùn)算符：一符一種 界 符：一符一種單詞種別編碼1、詞法分析器的任務(wù)和輸出形式（5）舉例假

5、定單詞類別用整數(shù)編碼，標(biāo)識(shí)符、常數(shù)、關(guān)鍵字、運(yùn)算符和界符的編碼依次為1、2、3、4、5。C+語句 if(a=90) b=c；在經(jīng)過詞法分析器處理后輸出的二元式及其單詞表示如下：二元式 單詞(3, if) 關(guān)鍵字if(5, () 界符(1,指向a的符號(hào)表項(xiàng)的指針) 標(biāo)識(shí)符a(4, =) 運(yùn)算符=(2, 90) 常數(shù)90(5, ) 界符)(1,指向b的符號(hào)表項(xiàng)的指針) 標(biāo)識(shí)符b(4, =) 運(yùn)算符=(1,指向c的符號(hào)表項(xiàng)的指針) 標(biāo)識(shí)符c(5, ；) 界符； 返回2、將詞法分析工作分離的考慮（1）將詞法分析器設(shè)計(jì)為語法分析器的子程序 在實(shí)現(xiàn)編譯程序時(shí)，常將詞法分析程序從語法分析中獨(dú)立出來，將其設(shè)計(jì)

6、為語法分析器的子程序，每當(dāng)語法分析器需要一個(gè)單詞符號(hào)時(shí)就調(diào)用詞法分析器，每一次調(diào)用，詞法分析器就從輸入串中識(shí)別出一個(gè)單詞符號(hào)，并將該單詞類別和單詞值返回給語法分析器。 字符串形式的源程序字符詞法分析器語法分析器符號(hào)表單詞取下一單詞2、將詞法分析工作分離的考慮（2）好處簡(jiǎn)化設(shè)計(jì)： 由詞法分析器處理注解和空白字符，可簡(jiǎn)化語法分析器的設(shè)計(jì)。此外，在設(shè)計(jì)新語言時(shí)，分離詞法和語法規(guī)則可以進(jìn)行更全面的語言設(shè)計(jì)。改進(jìn)編譯效率： 編譯的大部分時(shí)間消耗在讀源程序和分離一個(gè)個(gè)單詞符號(hào)上，專用的經(jīng)過精心設(shè)計(jì)的讀源程序字符流和處理單詞符號(hào)的詞法分析器可以加快編譯速度。增強(qiáng)編譯系統(tǒng)的可移植性：不同語言的字母表的特殊性，

7、構(gòu)詞規(guī)則的差異和其它與設(shè)備有關(guān)的不規(guī)則性可以限制在詞法分析器中進(jìn)行處理。 返回3.2 詞法分析器的設(shè)計(jì)輸入緩沖區(qū)和預(yù)處理程序輸入緩沖區(qū)和預(yù)處理程序 1掃描器的工作原理掃描器的工作原理 2狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別 3狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) 41、輸入緩沖區(qū)和預(yù)處理程序 （1）預(yù)處理程序 建立輸入緩沖區(qū)，將源程序分批讀入輸入緩沖區(qū)中 過濾掉源程序中的注釋；剔除一些無用的空白符、跳格符、回車符、換行符等編輯性字符；進(jìn)行宏替換；實(shí)現(xiàn)文件包含的嵌入和條件編譯的嵌入等。 將預(yù)處理結(jié)果送掃描器的掃描緩沖區(qū)（2）預(yù)處理程序作為獨(dú)立子程序 預(yù)處理可作為一個(gè)子程序完成上述三個(gè)

8、任務(wù)，并被詞法分析器調(diào)用，每調(diào)用一次，它就處理出一串確定長(zhǎng)度（如120個(gè)字符）的輸入字符，并送進(jìn)掃描緩沖區(qū)。 返回2、掃描器的工作原理 （1）掃描器執(zhí)行詞法分析的程序稱為，或稱，或稱。（2）掃描緩沖區(qū)一個(gè)可以互補(bǔ)使用的一分為二的掃描緩沖區(qū)。掃描緩沖區(qū)總長(zhǎng)度為2N（如N=120）個(gè)字符，掃描器單詞長(zhǎng)度的要求是單詞長(zhǎng)度1/2掃描緩沖區(qū)長(zhǎng)度。 2、掃描器的工作原理 （3）設(shè)置兩個(gè)指示器 起點(diǎn)指示器：指向當(dāng)前正在識(shí)別的單詞的開始位置（指向新單詞的首字符） 搜索指示器：用于向前搜索以尋找單詞的終點(diǎn)（4）掃描器的工作 調(diào)用預(yù)處理子程序，把N(如120)個(gè)輸入字符裝進(jìn)掃描緩沖區(qū)的某半?yún)^(qū)，搜索指針從起點(diǎn)指針開

9、始向前尋找單詞的終點(diǎn)，若在該半?yún)^(qū)內(nèi)查找到單詞的終點(diǎn)，便輸出二元式，再把起點(diǎn)指針移到此處的后一個(gè)字符，繼續(xù)搜索下一個(gè)單詞，如果在搜索到該半?yún)^(qū)的邊緣，尚未到達(dá)單詞終點(diǎn)，那么就調(diào)用預(yù)處理子程序，把后續(xù)的N個(gè)字符裝進(jìn)另半?yún)^(qū)，繼續(xù)搜索。 返回3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別 （1）狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖是一種有限方向圖，狀態(tài)轉(zhuǎn)換圖可用于識(shí)別3型語言，它是設(shè)計(jì)和實(shí)現(xiàn)掃描器的一種有效工具，是有限自動(dòng)機(jī)的直觀圖示。它由以下幾個(gè)要素構(gòu)成：結(jié)點(diǎn)：代表狀態(tài)，用圓圈表示。箭弧：狀態(tài)之間的連接，箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。初態(tài)：識(shí)別出某一類字符串的開始，初態(tài)只有一個(gè)。終態(tài)：識(shí)別出某一單

10、詞，至少有一個(gè)。用雙圈表示。aaa3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別 （2）狀態(tài)轉(zhuǎn)換圖識(shí)別的符號(hào)串 把從開始狀態(tài)出發(fā)到某一終止?fàn)顟B(tài)所經(jīng)過的路徑上的標(biāo)記依次連接起來的符號(hào)串，稱為能被該狀態(tài)轉(zhuǎn)換圖識(shí)別的符號(hào)串。 例如，右圖能夠識(shí)別符號(hào)串a(chǎn)db,addb,adddb,.,c（3）狀態(tài)轉(zhuǎn)換圖識(shí)別的語言 狀態(tài)轉(zhuǎn)換圖所能識(shí)別的全部符號(hào)串組成的集合構(gòu)成了該狀態(tài)轉(zhuǎn)換圖所識(shí)別的語言。 例如，右圖所能識(shí)別的語言為：L(G)=c,adnb|n03、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別 （4）標(biāo)識(shí)符及無符號(hào)數(shù)的狀態(tài)轉(zhuǎn)換圖012 2(a)字母字母或數(shù)字其它*012 2(b)數(shù)字?jǐn)?shù)字其它*012 72356數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字E或數(shù)字?jǐn)?shù)字其它*數(shù)

11、字其它其它(c)E4 (a) 標(biāo)識(shí)符；(b) 無符號(hào)整數(shù)；(c) 無符號(hào)數(shù)*為進(jìn)行超前搜索，多讀進(jìn)了為進(jìn)行超前搜索，多讀進(jìn)了一個(gè)符號(hào)，應(yīng)回退搜索指示器。一個(gè)符號(hào)，應(yīng)回退搜索指示器。3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別 （5）利用狀態(tài)轉(zhuǎn)換圖識(shí)別單詞的基本步驟從開始狀態(tài)出發(fā)；讀入一個(gè)字符；根據(jù)當(dāng)前字符轉(zhuǎn)入下一狀態(tài)；重復(fù)和，直到到達(dá)某一終態(tài)。3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別 （6）舉例下圖為識(shí)別某個(gè)簡(jiǎn)單語言的所有單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖。返回4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) （1）一組全局變量和函數(shù)要能有效實(shí)現(xiàn)詞法分析器，需要定義如下的一組全局變量和函數(shù)：字符變量，存放最新讀入的源程序字符：字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串：

12、函數(shù)，把下一個(gè)字符讀入到ch中。：函數(shù)，跳過空白符，直至ch中讀入一非空白符。：函數(shù)，把ch中的字符連接到 strToken ；：函數(shù)，判斷ch中字符是否為字母；： 函數(shù)，判斷ch中字符是否為數(shù)字；：函數(shù)，對(duì)于strToken中的字符串查找保留字表，若它是保留字則給出它的編碼，否則返回0；：函數(shù)，把搜索指針回調(diào)一個(gè)字符位置，將ch置為空白字符；4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) （1）一組全局變量和函數(shù)：函數(shù)，將strToken中的標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針；: 函數(shù)，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。 ：函數(shù)，把strToken中數(shù)字串譯成標(biāo)準(zhǔn)二進(jìn)制碼，并作為函數(shù)值返回（十進(jìn)

13、制轉(zhuǎn)換為二進(jìn)制）4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) （2）根據(jù)狀態(tài)轉(zhuǎn)換圖編寫代碼的一般方法 一般將狀態(tài)轉(zhuǎn)換圖看成一個(gè)流程圖，從狀態(tài)轉(zhuǎn)換圖的初態(tài)開始，對(duì)其每一個(gè)狀態(tài)結(jié)點(diǎn)編寫一段相應(yīng)的程序，具體的做法是：每個(gè)狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)程序段；對(duì)不含回路的分叉結(jié)點(diǎn)來說，可讓它對(duì)應(yīng)一個(gè)switch 語句或一組if.else語句；如下圖中的結(jié)點(diǎn) i 對(duì)應(yīng)的程序段為：state i：GetChar();if(IsLetter().轉(zhuǎn)狀態(tài)j對(duì)應(yīng)的程序段.else if(IsDigit().轉(zhuǎn)狀態(tài)k對(duì)應(yīng)的程序段.else if(ch=+).轉(zhuǎn)狀態(tài)L對(duì)應(yīng)的程序段.else .錯(cuò)誤處理.4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) （2）根據(jù)狀態(tài)轉(zhuǎn)換

14、圖編寫代碼的一般方法對(duì)含有回路的狀態(tài)結(jié)點(diǎn)來說，可讓它對(duì)應(yīng)一個(gè)由while語句和if語句構(gòu)成的程序段；如下圖中的結(jié)點(diǎn) i 對(duì)應(yīng)的程序段為：state i：GetChar();while(IsLetter()|IsDigit()GetChar();.轉(zhuǎn)狀態(tài)j對(duì)應(yīng)的程序段.4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) （2）根據(jù)狀態(tài)轉(zhuǎn)換圖編寫代碼的一般方法終態(tài)結(jié)點(diǎn)表示識(shí)別出某種單詞符號(hào)，因此一般對(duì)應(yīng)一個(gè)形如return(code,value)的語句，其中code為單詞的種別編碼，value為單詞符號(hào)的屬性值，或無定義； 如下圖中的結(jié)點(diǎn) i 對(duì)應(yīng)的程序段為：凡帶有星號(hào)（*）的終態(tài)結(jié)點(diǎn)意味著多讀進(jìn)一個(gè)不屬于現(xiàn)行單詞符號(hào)的字

15、符，該字符應(yīng)予退回，即必須把搜索指示器回調(diào)一個(gè)字符位置。如下圖中的結(jié)點(diǎn) i 對(duì)應(yīng)的程序段為：state i：return (code,value);state i：Retract();return (code,value);4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) （3）詞法規(guī)則的相關(guān)約定為方便起見，對(duì)詞法進(jìn)行如下約定：除標(biāo)識(shí)符、常數(shù)外，均為一符一種；關(guān)鍵字均作為保留字，不可用作用戶標(biāo)識(shí)符；設(shè)保留字表，識(shí)別出標(biāo)識(shí)符時(shí)，查該表確定是否為關(guān)鍵字；相鄰單詞之間至少存在一個(gè)界符、運(yùn)算符或空格。4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) （4）舉例 編寫由以下狀態(tài)轉(zhuǎn)換圖所描述的某簡(jiǎn)單語言的詞法分析程序。單詞符號(hào)單詞符號(hào)種別編碼種別編碼助

16、憶符助憶符內(nèi)碼值內(nèi)碼值DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END標(biāo)識(shí)符6$ID內(nèi)部字符串常數(shù)（數(shù)）7$INT標(biāo)準(zhǔn)二進(jìn)制形式=8$ASSIGN-9$PLUS*10$STAR*11$POWER，12$COMMA(13$LPAR)14$RPAR單詞符號(hào)及內(nèi)碼值4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) int code,value; strToken= ; GetChar( ); GetBC( ); if (IsLetter( ) while (IsLetter( ) or IsDigit( ) Concat ( ) ; GetChar( ); Retract( )； 4、狀態(tài)轉(zhuǎn)換圖

17、的代碼實(shí)現(xiàn) code= Reserve ( ); if (code=0) value=InsertId(strToken); return($ID,value);else return(code, );else if (IsDigit( ) while (IsDigit( ) Contact( ); Getchar( ); Retract( )； value=InsertConst(strToken); return($INT,value);4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn) else if (ch=) return($ASSIGN,);else if (ch=+) return($PLUS, );el

18、se if (ch=*) GetChar( );if (ch =*) return ($POWER, );Retract(); return ($STAR, );else if (ch=;) return ($SEMICOLON, -);else if (ch=() return ($LPAR, -);else if (ch=) return ($RPAR, -); else ProcError( ); /錯(cuò)誤處理；實(shí)驗(yàn)一 詞法分析器的設(shè)計(jì) （1）實(shí)驗(yàn)?zāi)康暮鸵罄斫庠~法分析器的任務(wù)和輸出形式；理解掃描器的工作原理；掌握狀態(tài)轉(zhuǎn)換圖的繪制以及單詞的識(shí)別技術(shù)；掌握詞法分析器的設(shè)計(jì)過程，能夠使用某種高

19、級(jí)語言實(shí)現(xiàn)一個(gè)詞法分析器。（2）實(shí)驗(yàn)內(nèi)容給出一個(gè)簡(jiǎn)單語言的詞法規(guī)則描述如表3.2所示，其中：種別碼是1開頭的為關(guān)鍵詞，2開頭的為算符，3開頭的為界符，4開頭的為標(biāo)識(shí)符，5開頭的為常數(shù)；標(biāo)識(shí)符為字母開頭，以字母和數(shù)字組成的任意符號(hào)串；常數(shù)為整數(shù)，即以數(shù)字組成的符號(hào)串。實(shí)驗(yàn)一 詞法分析器的設(shè)計(jì) 請(qǐng)完成以下任務(wù)：畫出識(shí)別該語言詞法規(guī)則的狀態(tài)轉(zhuǎn)換圖；依據(jù)該狀態(tài)轉(zhuǎn)換圖編制出詞法分析程序，能夠從輸入的源程序中，識(shí)別出各個(gè)具有獨(dú)立意義的單詞，即基本保留字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符五大類。并依次輸出各個(gè)單詞的內(nèi)部編碼（種別碼）及單詞符號(hào)自身值。實(shí)驗(yàn)一 詞法分析器的設(shè)計(jì) 單詞符號(hào)單詞符號(hào)種別碼種別碼內(nèi)碼內(nèi)碼單

20、詞符號(hào)單詞符號(hào)種別碼種別碼內(nèi)碼內(nèi)碼單詞符號(hào)單詞符號(hào)種別碼種別碼內(nèi)碼內(nèi)碼void101*203&216main102/204|217int103=205！218char104206(301if105=207)302else106208303for107=209304while108=210305return109211306cout110+212，307cin111-213；308+201214標(biāo)識(shí)符400-202215常數(shù)500二進(jìn)制形式返回3.3 單詞的描述工具正規(guī)文法正規(guī)文法 1正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集 21、正規(guī)文法 正規(guī)文法（線性文法）若文法G的任一產(chǎn)生式的形式都為AaB或

21、Aa，其中A，BVN ，aVT*，則稱G為一個(gè)；若文法G的任一產(chǎn)生式的形式都為ABa或Aa，其中A，BVN ，aVT*，則稱G為一個(gè)。右線性文法和左線性文法統(tǒng)稱為。【例3.2】 設(shè)有文法G1=(VT,VN,S,P)，其中VT=0,1，VN =S,A,B，P為：S0A|1BA10A|1B01B|0則G1是一個(gè)正規(guī)文法。 返回2、正規(guī)式與正規(guī)集 （1）正規(guī)式與正規(guī)集的遞歸定義和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和；任何，是上的正規(guī)式，它所表示的正規(guī)集為；假定U和V都是上的正規(guī)式，它們所表示的正規(guī)集分別為(U) 和 (V)，那么，(U|V)、(UV)和(U*)也都是正規(guī)式，它們所表示的正規(guī)集分

22、別為(U)(V)、(U)(V)和（(U)*）。 僅由有限次使用上述三步驟而得到的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。（2）正規(guī)式的運(yùn)算 正規(guī)式的運(yùn)算符“|” 、“ ”和“*”分別讀作“或”、“連接”和“閉包”。運(yùn)算符的優(yōu)先級(jí)依次由低到高。連接符“ ”一般可以省略不寫。 2、正規(guī)式與正規(guī)集 【例3.6】 令=a，b， 則上的正規(guī)式和相應(yīng)的正規(guī)集如下所示： 正規(guī)式正規(guī)式正規(guī)集正規(guī)集aaa|ba,babab(a|b)(a|b)aa,ab,ba,bba*,a,aa,任意個(gè)任意個(gè)a的串的串(a|b)*,a,b,aa,ab,所有由所有由a和和b組成的串組成的串(a|b)*(aa

23、|bb)(a|b)* 上所有含有兩個(gè)相繼的上所有含有兩個(gè)相繼的a或兩個(gè)相繼的或兩個(gè)相繼的b組成的串組成的串2、正規(guī)式與正規(guī)集 （3）正規(guī)式的等價(jià)若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則稱這兩個(gè)正規(guī)式。 即 U、V為正規(guī)式，若L(U)=L(V)，則稱U、V等價(jià)，記為U=V。例如，1(01)* =(10)*1，b(ab)* = (ba)*b，(a|b)* = (a*|b*)*。（4）正規(guī)式和正規(guī)集的運(yùn)算律若 U，V 和 W 均為正規(guī)式，則下列關(guān)系普遍成立：交換律 正規(guī)式正規(guī)式正規(guī)集正規(guī)集U|VV|UL(U|V)L(V|U)L(U|V)L(U)L(V)L(V|U)L(V)L(U)2、正規(guī)式與正規(guī)集 （4）

24、正規(guī)式和正規(guī)集的運(yùn)算律 結(jié)合律 正規(guī)式正規(guī)式正規(guī)集正規(guī)集U | (V | W)(U | V) | WL(U|(V| W)L(U|V)| W)L(U|(V| W)L(U)L(V| W)L(U)L(V)L(W)L(U|V)| W)L(U|V)L(W)L(U)L(V)L(W)U(VW)(UV)WL(U(VW)L(UV)W)L(U(VW)L(U)L(VW)L(U)L(V)L(W)L(UV)W)L(UV)L(W)L(U)L(V)L(W)2、正規(guī)式與正規(guī)集 （4）正規(guī)式和正規(guī)集的運(yùn)算律 分配律 正規(guī)式正規(guī)式正規(guī)集正規(guī)集U(V | W)(UV) | UWL(U(V| W)L(UV| UW)L(U(V| W)

25、L(U)L(V| W)L(U)L(V)L(U)L(W)L(UV| UW)L(UV)L(UW)L(U)L(V)L(U)L(W)(V | W)UVU | WUL(V| W)U)L(VU| WU)L(V| W)U)L(V| W)L(U)L(V)L(U)L(W)L(U)L(VU| WU)L(VU)L(WU)L(V)L(U)L(W)L(U)2、正規(guī)式與正規(guī)集 （4）正規(guī)式和正規(guī)集的運(yùn)算律 對(duì)任何正規(guī)式和正規(guī)集有：【例3.7】 證明證明：利用正規(guī)式的分配律和結(jié)合律直接推導(dǎo)： UUU L( U)L(U )L(U) *(ab) aa(ba)*2102121210*)(.|)(|)(|)(.|)(|)(|.|)

26、( |)( |.)|)( |)( |)()(baabaabaabaabaabaaaaabaabaaabababaab作業(yè)3.1習(xí)題三（P64）：2(1)(2)3(1)(2)(3)返回3.4 有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)（確定有限自動(dòng)機(jī)（DFA） 1非確定有限自動(dòng)機(jī)（非確定有限自動(dòng)機(jī)（NFA） 2將將NFA轉(zhuǎn)換為轉(zhuǎn)換為DFA 3確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn) 41、確定有限自動(dòng)機(jī)（DFA） （1）確定有限自動(dòng)機(jī)（DFA）的定義一個(gè)確定的有限自動(dòng)機(jī)（DFA）M是一個(gè)五元組： M =（S， ，s0 ，F(xiàn) )S是一個(gè)非空有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)。是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入

27、符號(hào)，所以也稱為輸入符號(hào)字母表。是狀態(tài)轉(zhuǎn)換函數(shù)，是在SS上的單值映射。定義形式: (s，a)= s，其中sS，sS，表示當(dāng)現(xiàn)行狀態(tài)為s，輸入字符為a時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)s。稱s為s的一個(gè)后續(xù)狀態(tài)。s0S，是唯一的一個(gè)初態(tài)。F S，可空,是一個(gè)終態(tài)集,終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。 1、確定有限自動(dòng)機(jī)（DFA） （2）表示形式狀態(tài)轉(zhuǎn)換矩陣 一個(gè)DFA可用一個(gè)矩陣表示，行表示狀態(tài)，列表示輸入字符，矩陣元素表示(s,a)的值。這個(gè)矩陣稱為?！纠?.8】 DFA M=(S, U, V, Q，a, b，S，Q)，其中定義為： (S,a)=U，(S,b)=V，(U,a)=Q，(U,b)=V (V,a)=

28、U，(V,b)=Q，(Q,a)=Q，(Q,b)=Q則該DFA對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表所示。 字符字符狀態(tài)狀態(tài)abSUVUQVVUQQQQ1、確定有限自動(dòng)機(jī)（DFA） （2）表示形式 狀態(tài)轉(zhuǎn)換圖 一個(gè)DFA可以表示成一張（確定的），假定DFA M含m個(gè)狀態(tài)和n個(gè)輸入字符，那么它所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖就含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多含有n條箭弧射出和別的結(jié)點(diǎn)相連接，每條箭弧用中的一個(gè)不同輸入字符作標(biāo)記。整張圖含有唯一的一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)（可以是0個(gè)）終態(tài)結(jié)點(diǎn)?！纠?.9】 例3.8 中所定義的DFA M相應(yīng)的狀態(tài)轉(zhuǎn)換圖如下圖所示： 1、確定有限自動(dòng)機(jī)（DFA） （3）可識(shí)別 對(duì)于*中的任何字，若存在

29、一條從初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的路徑，這條路徑即為。若這條通路上所有弧的標(biāo)記符連接成的字等于，則稱可為DFA M所（或）。若M的初態(tài)結(jié)點(diǎn)同時(shí)也是終態(tài)結(jié)點(diǎn)，則空字可為M所識(shí)別。DFA M =（S， ，s0 ，F(xiàn) )所能接受的字符串的全體為L(zhǎng)（M）。（4）定理如果一個(gè)DFA M的輸入字母表為，則稱M是上的一個(gè)DFA，可以證明：上的一個(gè)字集V *是正規(guī)的，當(dāng)且僅當(dāng)存在上的DFA M，使得V=L（M）。 返回2、非確定有限自動(dòng)機(jī)（NFA） （1）非確定有限自動(dòng)機(jī)（NFA）的定義一個(gè)非確定的有限自動(dòng)機(jī)（NFA）M是一個(gè)五元組： M =（S， ，S0 ，F(xiàn) ) S是一個(gè)非空有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)

30、。是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào)字母表。是狀態(tài)轉(zhuǎn)換函數(shù)，：S*2S，即是一個(gè)從S *到S的子集的映射（多值映射），其中，2S表示S的所有子集的全體。S0 S，是一個(gè)非空的初態(tài)集合。F S，可空，是一個(gè)終態(tài)集合，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。 2、非確定有限自動(dòng)機(jī)（NFA） （2）表示形式一個(gè)NFA也可以用狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖來表示。狀態(tài)轉(zhuǎn)換矩陣的行表示狀態(tài)，列表示輸入字，矩陣元素表示(s，a)的值。下面，主要介紹狀態(tài)轉(zhuǎn)換圖的表示方法。NFA的狀態(tài)轉(zhuǎn)換圖表示 若一個(gè)NFA M含有m個(gè)狀態(tài)和n個(gè)輸入字符，那么它所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖就含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可

31、以射出若干條箭弧與別的結(jié)點(diǎn)相連接，每條箭弧用*中的一個(gè)字（不一定要不同的字而且可以是空字）作為標(biāo)記（稱為輸入字），整個(gè)狀態(tài)轉(zhuǎn)換圖至少含有一個(gè)初態(tài)終點(diǎn)和若干個(gè)終態(tài)結(jié)點(diǎn)，某些結(jié)點(diǎn)既可以是初態(tài)結(jié)點(diǎn)也可以是終態(tài)結(jié)點(diǎn)。 2、非確定有限自動(dòng)機(jī)（NFA） （3）可識(shí)別 對(duì)于*中的任何一個(gè)字，若存在一條從某一個(gè)初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字等于，則稱可為NFA M所（或）。若M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的的通路，則空字可為M所識(shí)別。 例如，下圖所示的NFA M所能識(shí)別的是所有含有相繼兩個(gè)a或相繼兩個(gè)b的字。 返回3、將

32、 NFA 轉(zhuǎn)換為 DFA （1）NFA與DFA的等價(jià)性定理對(duì)每一個(gè)NFA N，一定存在一個(gè)DFA M，使得：L(M)=L(N)，即對(duì)于每個(gè)NFA N存在著與之等價(jià)的DFA M，而且與某一NFA等價(jià)的DFA是不唯一的。（2）子集算法 可以通過子集法的算法來將NFA轉(zhuǎn)換成接受相同語言的DFA。子集法的基本思想是：把DFA中的每一個(gè)狀態(tài)對(duì)應(yīng)NFA中的一組狀態(tài)。即由于NFA中的是多值的，所以在讀入一個(gè)輸入符號(hào)后可能達(dá)到的狀態(tài)是集合，而子集法就是用DFA的狀態(tài)記錄該狀態(tài)的集合。3、將 NFA 轉(zhuǎn)換為 DFA （3）子集算法涉及的相關(guān)運(yùn)算閉包_CLOSURE(I)假定I是M的狀態(tài)集的子集，定義I的閉包_C

33、LOSURE(I)為：a)若qI，則q_CLOSURE(I)；b)若qI，那么從q出發(fā)經(jīng)任意條弧而能到達(dá)的任何狀態(tài)q都屬于_CLOSURE(I)； Ia 假定I是M狀態(tài)集的子集，a，定義Ia=_CLOSURE(J) ，其中，J是那些可從I中某一狀態(tài)結(jié)點(diǎn)出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體?？梢韵韧ㄟ^I求J，J=y|y=(x,a),xI，再求_CLOSURE(J)，即得Ia。3、將 NFA 轉(zhuǎn)換為 DFA 例如，如下圖所示的NFA中：若I=1，則_CLOSURE(I)=1,2；若I=5，則_CLOSURE(I)=5,6,2；若I=1,2，則J=5, 4 , 3，Ia =_CLOSURE(J)

34、=5,6,2,3,8,4,7。3、將 NFA 轉(zhuǎn)換為 DFA （4）NFA確定化為DFA的方法假設(shè)NFA M =（S， ，S0 ，F(xiàn) )，可按如下方法對(duì)其確定化： 對(duì)M的狀態(tài)轉(zhuǎn)換圖作如下改造：a)引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y。X，Y S，從X到S0中任意狀態(tài)結(jié)點(diǎn)連一條箭弧，從F中任意狀態(tài)結(jié)點(diǎn)連一條箭弧到Y(jié)。3、將 NFA 轉(zhuǎn)換為 DFA （4）NFA確定化為DFA的方法b)對(duì)M的狀態(tài)轉(zhuǎn)換圖按下圖所示的規(guī)則作重復(fù)替換，其中K是新引入的狀態(tài)。重復(fù)這種分裂過程直至狀態(tài)轉(zhuǎn)換圖中的每條箭弧上的標(biāo)記或?yàn)?，或?yàn)橹械膯蝹€(gè)字母。將完成以上操作后最終得到的NFA 記為M，顯然有：L(M)=L(M)。3、將 NF

35、A 轉(zhuǎn)換為 DFA （4）NFA確定化為DFA的方法 構(gòu)造狀態(tài)轉(zhuǎn)換表假設(shè)a1, ak，針對(duì)M 構(gòu)造如下的狀態(tài)轉(zhuǎn)換表：a)該表有k+1列，置該表的首行首列為_CLOSURE(X)，其中X為初始狀態(tài)；b)一般而言，如果某一行的第一列的狀態(tài)子集已經(jīng)確定，例如記為I，那么，置該行的i+1列為Iai（i=1k）；c)檢查該行上的所有狀態(tài)子集，看它們是否已經(jīng)在表的第一列中出現(xiàn)，將未曾出現(xiàn)者依次重新填入到后面空行的第一列；d)重復(fù)上述過程，直到出現(xiàn)在i+1列（i=1k）上的所有狀態(tài)子集均已在第一列上出現(xiàn)； e)由于M的狀態(tài)子集的個(gè)數(shù)是有限的，所以上述過程必定在有限步內(nèi)終止。3、將 NFA 轉(zhuǎn)換為 DFA （

36、4）NFA確定化為DFA的方法 根據(jù)狀態(tài)轉(zhuǎn)換表構(gòu)造狀態(tài)轉(zhuǎn)換矩陣（DFA M）假設(shè)a1, ak，針對(duì)M 構(gòu)造如下的狀態(tài)轉(zhuǎn)換表：a)將狀態(tài)轉(zhuǎn)換表中的每個(gè)狀態(tài)子集視為新的狀態(tài)，將其作為M的狀態(tài)；b)M的初態(tài)是狀態(tài)轉(zhuǎn)換表中首行首列的狀態(tài)子集對(duì)應(yīng)的那個(gè)狀態(tài)； c)M的終態(tài)是狀態(tài)轉(zhuǎn)換表中含有M終態(tài)的狀態(tài)子集對(duì)應(yīng)的那些狀態(tài) 。顯然，有 L(M)=L(M)=L(M) 。3、將 NFA 轉(zhuǎn)換為 DFA 【例3.12】 構(gòu)造識(shí)別正規(guī)式(a|b)*(aa|bb)(a|b)*的NFA，并將其確定化為DFA。解：構(gòu)造NFA*(a | b) (aa | bb)(a | b)*(a | b)*(a | b)aa | bba

37、 | baabba | babbaabab3、將 NFA 轉(zhuǎn)換為 DFA 構(gòu)造狀態(tài)轉(zhuǎn)換表aabbbaabIIaIbX,5,15,3,15,4,15,3,15,4,15,3,1,2,6,Y5,4,1,2,6,Y5,3,15,4,15,3,1,2,6,Y5,4,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,2,6,Y5,4,1,6,Y3、將 NFA 轉(zhuǎn)換為 DFA 重命名，構(gòu)造狀態(tài)轉(zhuǎn)換矩陣IIaIbX,5,15,3,15,4,15,3,15,3,1,2,6,Y5,

38、4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,YSab012132214335464564635其中，0為初態(tài)，3,4,5,6為終態(tài)3、將 NFA 轉(zhuǎn)換為 DFA 繪制狀態(tài)轉(zhuǎn)換圖Sab012132214335464564635返回4、確定有限自動(dòng)機(jī)的化簡(jiǎn) （1）DFA的化簡(jiǎn)（最小化DFA）對(duì)于任意給定的DFA M，構(gòu)造另一個(gè)DFA M，使得L(M)=L(M)

39、，且DFA M 的狀態(tài)個(gè)數(shù)為最少。 （2）狀態(tài)等價(jià)和可區(qū)別 假定s和t是M的兩個(gè)不同狀態(tài)，如果從狀態(tài)s出發(fā)能讀出某個(gè)字w而停于終態(tài)，從狀態(tài)t出發(fā)也能讀出同樣的字w而停于終態(tài)，反之亦然，就稱狀態(tài)s和t是的；如果 DFA M的兩個(gè)狀態(tài)s和t不等價(jià)，則稱狀態(tài)s和t是的。 可 區(qū) 別 等 價(jià)4、確定有限自動(dòng)機(jī)的化簡(jiǎn) 終態(tài)和非終態(tài)是可區(qū)別的。（3）狀態(tài)等價(jià)的條件：狀態(tài) s 和 t 必須同時(shí)為終態(tài)或非終態(tài)。：對(duì)于所有輸入符號(hào)，狀態(tài) s 和 t 必須轉(zhuǎn)化到等價(jià)的狀態(tài)里。 等 價(jià)4、確定有限自動(dòng)機(jī)的化簡(jiǎn) （4）DFA最小化的任務(wù) 確定有限自動(dòng)機(jī)化簡(jiǎn)的任務(wù)是去掉多余狀態(tài)，合并等價(jià)狀態(tài)。多余狀態(tài)是指從該自動(dòng)機(jī)的開

40、始狀態(tài)出發(fā)，任何輸入串也不能達(dá)到的狀態(tài)，即從初態(tài)結(jié)點(diǎn)開始永遠(yuǎn)到達(dá)不了的那些狀態(tài)。（5）DFA最小化算法（）基本思想a)將DFA M中的狀態(tài)集分割成一些互不相交的子集，使得任何不同的兩個(gè)子集中的狀態(tài)都是可區(qū)別的，而同一個(gè)子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。b)從每個(gè)子集中任選一個(gè)狀態(tài)作為代表，同時(shí)消去其它等價(jià)狀態(tài)及其射出的弧。c)把那些原來到達(dá)其它等價(jià)狀態(tài)的弧改為到達(dá)相應(yīng)的代表狀態(tài)。（5）DFA最小化算法（） 具體步驟a)初始分割：把狀態(tài)集S劃分為終態(tài)集和非終態(tài)集，記為 其中， 屬于終態(tài)集， 屬于非終態(tài)集。b)k次分割：假定經(jīng)過k次劃分后， 得到m個(gè)子集， 記為 ，并且屬于不同子集中的狀態(tài)都是可區(qū)別

41、的。檢查 中的每個(gè)子 集 ，看其能否進(jìn)一步分割。令 ，若存在一個(gè)輸入字符a（a），使得 不全包含在現(xiàn)行分割 的某一子集 中，就將 一分為二。12000S ,S 10S20S12mkkkkS ,S ,S kjkS (j1,2,m)jk1tS(q ,q )jk( S)aIkjkS4、確定有限自動(dòng)機(jī)的化簡(jiǎn) ikS 假設(shè)當(dāng)前子集 ，若狀態(tài)q1和q2經(jīng)a弧分別到達(dá)狀態(tài)t1和t2，而t1和t2又分屬于當(dāng)前已劃分出的兩個(gè)不同子集 和 中，則此時(shí)應(yīng)將 分為兩半，使得一半含有q1，另一半含有q2。4、確定有限自動(dòng)機(jī)的化簡(jiǎn) jk12tS(q ,q ,q )hkSikSjkSj1jikkkSs|sS and (s,

42、a)S j2jj1kkkSSS（5）DFA最小化算法（） 具體步驟c)循環(huán)分割：重復(fù)上一步，直到子集個(gè)數(shù)不再增加為止（即每個(gè)子集已是不可再分的了）。所謂不能劃分，是指該子集或者僅有一個(gè)狀態(tài)，或者雖有多個(gè)狀態(tài)但這些狀態(tài)均不可區(qū)別（即等價(jià)）。d)選代表，刪除等價(jià)狀態(tài)：對(duì)于最后分劃 中的每一個(gè)子集，選取該子集中的一個(gè)狀態(tài)代表其它等價(jià)狀態(tài)。例如，狀態(tài)子集I=q1,q2,，qk，挑選q1作為子集I的代表，則凡導(dǎo)入到q2，qk的弧都改成導(dǎo)入到q1中，然后將q2，qk及其所射出的弧從原來的DFA中刪除。e)決定初態(tài)和終態(tài)：設(shè)刪除等價(jià)狀態(tài)之后的DFA為M ，凡那些包含M的初態(tài)的狀態(tài)子集所對(duì)應(yīng)的代表狀態(tài)均作為M

43、的初態(tài)；凡那些包含M的終態(tài)的狀態(tài)子集所對(duì)應(yīng)的代表狀態(tài)均作為M 的終態(tài)。則有L(M )=L(M)。4、確定有限自動(dòng)機(jī)的化簡(jiǎn) 4、確定有限自動(dòng)機(jī)的化簡(jiǎn) 【例3.13】 對(duì)下圖所示的DFA M進(jìn)行化簡(jiǎn)。解：初始分割將狀態(tài)集S=0，1，2，3，4，5，6劃分為終態(tài)集3，4，5，6和非終態(tài)集0，1，2。4、確定有限自動(dòng)機(jī)的化簡(jiǎn) 考察3，4，5，6 所以，3，4，5，6不再分割。 考察0，1，2由于 ，所以，應(yīng)將0，1，2分割為0，2和1。至此，得到的全部分割子集為3，4，5，6，0，2和1。ab3,4,5,63,63,4,5,63,4,5,64,53,4,5,6a0,1,21,33,4,5,60,1,2

44、aa0,21,134、確定有限自動(dòng)機(jī)的化簡(jiǎn) 考察0，2 所以，將0，2分割為0和2。 最后，得到的全部分割子集為0，1，2，3，4，5，6。每個(gè)子集均不需再分割，即每個(gè)子集內(nèi)的狀態(tài)互相等價(jià)，任意不同兩個(gè)子集中的狀態(tài)都是可區(qū)別的。b0,22,43,4,5,60,214、確定有限自動(dòng)機(jī)的化簡(jiǎn) 選代表，刪除多余狀態(tài) 令狀態(tài)3代表3，4，5，6，把原來導(dǎo)入4，5，6的弧全都導(dǎo)入3，并刪除4，5，6，最后可得下圖所示的最小化DFA。作業(yè)3.2習(xí)題三（P64）：56(1)(2)返回3.5 正規(guī)文法、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)特性正規(guī)文法與正規(guī)式的等價(jià)性正規(guī)文法與正規(guī)式的等價(jià)性 1正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性

45、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性 2正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性 3總結(jié)總結(jié) 41、正規(guī)文法與正規(guī)式的等價(jià)性 一個(gè)正規(guī)語言（正規(guī)集）既可以用正規(guī)文法定義，也可以用正規(guī)式定義。關(guān)于正規(guī)文法和正規(guī)式有以下等價(jià)性定理：（1）定理1、正規(guī)文法與正規(guī)式的等價(jià)性 （2）正規(guī)式到正規(guī)文法的轉(zhuǎn)換可按如下方法將上的一個(gè)正規(guī)式 r 轉(zhuǎn)換成正規(guī)文法G=（VT，VN，S，P）：首先令VT =，選擇一個(gè)非終結(jié)符號(hào)S（SVN）作為G的開始符號(hào)，并生成初始產(chǎn)生式Sr。然后，對(duì)該產(chǎn)生式反復(fù)運(yùn)用下述規(guī)則進(jìn)行變換，直到所生成的每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符為止。假設(shè)x和y都是正規(guī)式：規(guī)則1：形如Axy，變換為

46、AxB，By， BVN ；規(guī)則2：形如Ax*y，變換為AxA, Ay；規(guī)則3：形如Ax|y，變換為A x, A y 。1、正規(guī)文法與正規(guī)式的等價(jià)性 【例3.15】 將正規(guī)式 R=a(a|d)* 轉(zhuǎn)換成相應(yīng)的正規(guī)文法。解：令轉(zhuǎn)換成的文法為G=(VT, VN, S, P)，其中VT =a,d，文法開始符號(hào)為S，首先形成Sa(a|d)*，然后做變換：最后，得到的正規(guī)文法G的產(chǎn)生式為：VN =S,A。*SaAA(a | d)SaAA(a | d)AA SaAAaAAdAA SaAAaA | dA |1、正規(guī)文法與正規(guī)式的等價(jià)性 （3）正規(guī)文法到正規(guī)式的轉(zhuǎn)換可按如下方法將正規(guī)文法G=（VT，VN，S，P

47、）轉(zhuǎn)換成上的一個(gè)正規(guī)式 r ：首先令 =VT，然后，對(duì)P中的產(chǎn)生式反復(fù)運(yùn)用下述規(guī)則進(jìn)行變換，直到只剩下一個(gè)開始符號(hào)定義的產(chǎn)生式，并且該產(chǎn)生式的右部不含非終結(jié)符：規(guī)則1：形如AxB，By，變換為Axy ；規(guī)則2：形如AxA, Ay，變換為Ax*y；規(guī)則3：形如A x, A y，變換為 Ax|y。1、正規(guī)文法與正規(guī)式的等價(jià)性 【例3.16】 有正規(guī)文法GS，其中的產(chǎn)生式為：S d A|eB，AaA|b，BbB|c，將該文法G轉(zhuǎn)換成正規(guī)式。解：令 =a,b,c,d,e，然后對(duì)文法GS中的產(chǎn)生式做如下變換：將A，B代入S產(chǎn)生式的右部，得那么，與正規(guī)文法GS等價(jià)的正規(guī)式為：AaA | b*Aa bBbB

48、 | c*Bb c*Sda b | eb c*da b | eb c返回2、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性 （1）正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)定理對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M，如果L(G)L(M)，則稱G和M是的。關(guān)于正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性，有以下結(jié)論：2、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性 （2）由正規(guī)文法構(gòu)造有限自動(dòng)機(jī)由右線性正規(guī)文法構(gòu)造有限自動(dòng)機(jī)設(shè)G=( VT, VN, S, P)為一個(gè)右線性正規(guī)文法，則存在一個(gè)有限自動(dòng)機(jī)M =（S， ，S0 ，F(xiàn) )，使得L(M)=L(G)。M的構(gòu)造方法如下：a)M的字母表與G的終結(jié)符集合相同，即=VT；b)讓G中的每個(gè)非終結(jié)符對(duì)應(yīng)M中的一個(gè)狀態(tài)結(jié)點(diǎn)；c)

49、以G的開始符作為M的初態(tài)結(jié)點(diǎn)，即S0=S；d)引進(jìn)一個(gè)新的終態(tài)結(jié)點(diǎn)f，即S=VN f ；e)對(duì)G中形如AaB的產(chǎn)生式，則令(A,a)=B；f) 對(duì)G中形如Aa的產(chǎn)生式，則令(A,a)=f。2、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性 【例3.17】 設(shè)有右線性正規(guī)文法G=(0,1,A,B,C,D,A,P)，其中P為：A0|0B|1D B0D|1C C0|0B|1D D0D|1D 構(gòu)造與G等價(jià)的有限自動(dòng)機(jī)M。解：根據(jù)右線性正規(guī)文法構(gòu)造有限自動(dòng)機(jī)的方法，構(gòu)造M=(A,B,C,D,f,0,1,A,f ) ，其中為：(A,0)=f，(A,0)=B，(A,1)=D，(B,0)=D，(B,1)=C(C,0)=f，(C

50、,0)=B，(C,1)=D，(D,0)=D，(D,1)=D其狀態(tài)轉(zhuǎn)換圖如下圖所示：2、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性 （2）由正規(guī)文法構(gòu)造有限自動(dòng)機(jī) 由左線性正規(guī)文法構(gòu)造有限自動(dòng)機(jī)設(shè)G=( VT, VN, S, P)為一個(gè)左線性正規(guī)文法，則存在一個(gè)有限自動(dòng)機(jī)M =（S， ，S0 ，F(xiàn) )，使得L(M)=L(G)。M的構(gòu)造方法如下：a)M的字母表與G的終結(jié)符集合相同，即=VT；b)讓G中的每個(gè)非終結(jié)符對(duì)應(yīng)M中的一個(gè)狀態(tài)結(jié)點(diǎn)；c)以G的開始符號(hào)作為M的終態(tài)結(jié)點(diǎn)，即SF；d)引進(jìn)一個(gè)新的初態(tài)結(jié)點(diǎn)q0；e)對(duì)G中形如ABa的產(chǎn)生式，則令(B,a)=A；f) 對(duì)G中形如Aa的產(chǎn)生式，則令(q0,a)=A。2、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性 （3）由有限自動(dòng)機(jī)構(gòu)造正規(guī)文法由有限自動(dòng)機(jī)構(gòu)造右線性正規(guī)文法對(duì)于NFA，先將其確定化。設(shè)有確定有限自動(dòng)機(jī)DFA M=(S,s0, f )，構(gòu)造一個(gè)右線性正規(guī)文法G=( VT, VN, S,