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

詞法分析與有限自動(dòng)機(jī)演示文稿現(xiàn)在是1頁(yè)\一共有93頁(yè)\編輯于星期二優(yōu)選詞法分析與有限自動(dòng)機(jī)現(xiàn)在是2頁(yè)\一共有93頁(yè)\編輯于星期二教學(xué)內(nèi)容3.1詞法分析器的設(shè)計(jì)思想3.2詞法分析器的設(shè)計(jì)3.3單詞的描述工具3.4有限自動(dòng)機(jī)3.5正規(guī)式、正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性3.6詞法分析器的自動(dòng)構(gòu)造工具——LEX3.7本章小結(jié)現(xiàn)在是3頁(yè)\一共有93頁(yè)\編輯于星期二3.1詞法分析器的設(shè)計(jì)思想詞法分析器的任務(wù)和輸出形式

1將詞法分析工作分離的考慮

2現(xiàn)在是4頁(yè)\一共有93頁(yè)\編輯于星期二1、詞法分析器的任務(wù)和輸出形式（1）詞法分析器的任務(wù)

自左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，按語(yǔ)言的構(gòu)詞規(guī)則識(shí)別出一個(gè)個(gè)單詞，把作為字符串的源程序改造為單詞符號(hào)串的中間程序。字符串流單詞流源語(yǔ)言程序單詞符號(hào)現(xiàn)在是5頁(yè)\一共有93頁(yè)\編輯于星期二1、詞法分析器的任務(wù)和輸出形式（2）單詞符號(hào) 單詞符號(hào)是程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法單位和最小語(yǔ)義單位。（3）單詞符號(hào)的種類

標(biāo)識(shí)符：標(biāo)記常量、變量、函數(shù)等的名字，如fun、i

關(guān)鍵字：具有固定意義的標(biāo)識(shí)符，如if、while、for

常數(shù)：各種類型的常數(shù)，如實(shí)型0.618，布爾型TRUE

運(yùn)算符：如+、-、*、/、<=、<、>、>=、==

界符：如，、；、（、），{，}單詞符號(hào)現(xiàn)在是6頁(yè)\一共有93頁(yè)\編輯于星期二1、詞法分析器的任務(wù)和輸出形式（4）單詞符號(hào)的輸出形式 二元式：（單詞種別，單詞符號(hào)的屬性值）

表示單詞的種類，它是語(yǔ)法分析所需要的信息。一個(gè)語(yǔ)言的單詞符號(hào)如何劃分種類、分為幾類、如何編碼都屬于技術(shù)性問(wèn)題，主要取決于處理上的方便。通常讓每種單詞對(duì)應(yīng)一個(gè)整數(shù)碼，這樣可最大限度地把各個(gè)單詞區(qū)別開來(lái)。用來(lái)區(qū)分該類單詞中的哪一個(gè)單詞，它是單詞本身的機(jī)內(nèi)編碼。單詞符號(hào)的屬性是指單詞符號(hào)的特性或特征。屬性值是反應(yīng)特性或特征的值。例如，對(duì)于某個(gè)標(biāo)識(shí)符，常將存放它的有關(guān)信息的符號(hào)表項(xiàng)的指針作為其屬性值；而對(duì)于某個(gè)常數(shù)，則是將存放它的常數(shù)表項(xiàng)的指針作為其屬性值。現(xiàn)在是7頁(yè)\一共有93頁(yè)\編輯于星期二1、詞法分析器的任務(wù)和輸出形式（4）單詞符號(hào)的輸出形式

常用單詞種別編碼方案標(biāo)識(shí)符：一種關(guān)鍵字：全體視為一種或一字一種常數(shù)：按類型分種，如整數(shù)、實(shí)數(shù)、布爾型運(yùn)算符：一符一種界符：一符一種單詞種別編碼現(xiàn)在是8頁(yè)\一共有93頁(yè)\編輯于星期二1、詞法分析器的任務(wù)和輸出形式（5）舉例 假定單詞類別用整數(shù)編碼，標(biāo)識(shí)符、常數(shù)、關(guān)鍵字、運(yùn)算符和界符的編碼依次為1、2、3、4、5。C++語(yǔ)句if(a>=90)b=c；在經(jīng)過(guò)詞法分析器處理后輸出的二元式及其單詞表示如下：

二元式

單詞

(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,’；’) 界符；

返回現(xiàn)在是9頁(yè)\一共有93頁(yè)\編輯于星期二2、將詞法分析工作分離的考慮（1）將詞法分析器設(shè)計(jì)為語(yǔ)法分析器的子程序 在實(shí)現(xiàn)編譯程序時(shí)，常將詞法分析程序從語(yǔ)法分析中獨(dú)立出來(lái)，將其設(shè)計(jì)為語(yǔ)法分析器的子程序，每當(dāng)語(yǔ)法分析器需要一個(gè)單詞符號(hào)時(shí)就調(diào)用詞法分析器，每一次調(diào)用，詞法分析器就從輸入串中識(shí)別出一個(gè)單詞符號(hào)，并將該單詞類別和單詞值返回給語(yǔ)法分析器。

字符串形式的源程序字符詞法分析器語(yǔ)法分析器符號(hào)表單詞取下一單詞現(xiàn)在是10頁(yè)\一共有93頁(yè)\編輯于星期二2、將詞法分析工作分離的考慮（2）好處簡(jiǎn)化設(shè)計(jì)：由詞法分析器處理注解和空白字符，可簡(jiǎn)化語(yǔ)法分析器的設(shè)計(jì)。此外，在設(shè)計(jì)新語(yǔ)言時(shí)，分離詞法和語(yǔ)法規(guī)則可以進(jìn)行更全面的語(yǔ)言設(shè)計(jì)。改進(jìn)編譯效率：編譯的大部分時(shí)間消耗在讀源程序和分離一個(gè)個(gè)單詞符號(hào)上，專用的經(jīng)過(guò)精心設(shè)計(jì)的讀源程序字符流和處理單詞符號(hào)的詞法分析器可以加快編譯速度。增強(qiáng)編譯系統(tǒng)的可移植性：不同語(yǔ)言的字母表的特殊性，構(gòu)詞規(guī)則的差異和其它與設(shè)備有關(guān)的不規(guī)則性可以限制在詞法分析器中進(jìn)行處理。

返回現(xiàn)在是11頁(yè)\一共有93頁(yè)\編輯于星期二3.2詞法分析器的設(shè)計(jì)輸入緩沖區(qū)和預(yù)處理程序

1掃描器的工作原理

2狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別

3狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)

4現(xiàn)在是12頁(yè)\一共有93頁(yè)\編輯于星期二1、輸入緩沖區(qū)和預(yù)處理程序（1）預(yù)處理程序建立輸入緩沖區(qū)，將源程序分批讀入輸入緩沖區(qū)中過(guò)濾掉源程序中的注釋；剔除一些無(wú)用的空白符、跳格符、回車符、換行符等編輯性字符；進(jìn)行宏替換；實(shí)現(xiàn)文件包含的嵌入和條件編譯的嵌入等。將預(yù)處理結(jié)果送掃描器的掃描緩沖區(qū)（2）預(yù)處理程序作為獨(dú)立子程序 預(yù)處理可作為一個(gè)子程序完成上述三個(gè)任務(wù)，并被詞法分析器調(diào)用，每調(diào)用一次，它就處理出一串確定長(zhǎng)度（如120個(gè)字符）的輸入字符，并送進(jìn)掃描緩沖區(qū)。返回現(xiàn)在是13頁(yè)\一共有93頁(yè)\編輯于星期二2、掃描器的工作原理（1）掃描器

執(zhí)行詞法分析的程序稱為詞法 分析程序，或稱詞法分析器， 或稱掃描器。（2）掃描緩沖區(qū)

一個(gè)可以互補(bǔ)使用的一分為二的掃描緩沖區(qū)。掃描緩沖區(qū)總長(zhǎng)度為2×N（如N=120）個(gè)字符，掃描器單詞長(zhǎng)度的要求是單詞長(zhǎng)度≤1/2掃描緩沖區(qū)長(zhǎng)度。

現(xiàn)在是14頁(yè)\一共有93頁(yè)\編輯于星期二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)指針開始向前尋找單詞的終點(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ù)搜索。

返回現(xiàn)在是15頁(yè)\一共有93頁(yè)\編輯于星期二3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別（1）狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖是一種有限方向圖，狀態(tài)轉(zhuǎn)換圖可用于識(shí)別3型語(yǔ)言，它是設(shè)計(jì)和實(shí)現(xiàn)掃描器的一種有效工具，是有限自動(dòng)機(jī)的直觀圖示。它由以下幾個(gè)要素構(gòu)成：結(jié)點(diǎn)：代表狀態(tài)，用圓圈表示。箭?。籂顟B(tài)之間的連接，箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。初態(tài)：識(shí)別出某一類字符串的開始，初態(tài)只有一個(gè)。終態(tài)：識(shí)別出某一單詞，至少有一個(gè)。用雙圈表示。aaa現(xiàn)在是16頁(yè)\一共有93頁(yè)\編輯于星期二3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別（2）狀態(tài)轉(zhuǎn)換圖識(shí)別的符號(hào)串 把從開始狀態(tài)出發(fā)到某一終止?fàn)顟B(tài)所經(jīng)過(guò)的路徑上的標(biāo)記依次連接起來(lái)的符號(hào)串，稱為能被該狀態(tài)轉(zhuǎn)換圖識(shí)別的符號(hào)串。 例如，右圖能夠識(shí)別符號(hào)串

adb,addb,adddb,.....,c（3）狀態(tài)轉(zhuǎn)換圖識(shí)別的語(yǔ)言 狀態(tài)轉(zhuǎn)換圖所能識(shí)別的 全部符號(hào)串組成的集合構(gòu)成 了該狀態(tài)轉(zhuǎn)換圖所識(shí)別的語(yǔ)言。 例如，右圖所能識(shí)別的語(yǔ)言為：L(G)={c,adnb|n≥0}現(xiàn)在是17頁(yè)\一共有93頁(yè)\編輯于星期二3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別（4）標(biāo)識(shí)符及無(wú)符號(hào)數(shù)的狀態(tài)轉(zhuǎn)換圖

(a)標(biāo)識(shí)符；(b)無(wú)符號(hào)整數(shù)；(c)無(wú)符號(hào)數(shù)*為進(jìn)行超前搜索，多讀進(jìn)了一個(gè)符號(hào)，應(yīng)回退搜索指示器。現(xiàn)在是18頁(yè)\一共有93頁(yè)\編輯于星期二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)。現(xiàn)在是19頁(yè)\一共有93頁(yè)\編輯于星期二3、狀態(tài)轉(zhuǎn)換圖與單詞的識(shí)別（6）舉例 下圖為識(shí)別某個(gè)簡(jiǎn)單語(yǔ)言的所有單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖。返回現(xiàn)在是20頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)（1）一組全局變量和函數(shù)

要能有效實(shí)現(xiàn)詞法分析器，需要定義如下的一組全局變量和函數(shù)：ch：字符變量，存放最新讀入的源程序字符strToken：字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串GetChar：函數(shù)，把下一個(gè)字符讀入到ch中。GetBC：函數(shù)，跳過(guò)空白符，直至ch中讀入一非空白符。Concat：函數(shù)，把ch中的字符連接到strToken；IsLetter：函數(shù)，判斷ch中字符是否為字母；IsDigit：函數(shù)，判斷ch中字符是否為數(shù)字；Reserve：函數(shù)，對(duì)于strToken中的字符串查找保留字表，若它是保留字則給出它的編碼，否則返回0；Retract：函數(shù)，把搜索指針回調(diào)一個(gè)字符位置，將ch置為空白字符；現(xiàn)在是21頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)（1）一組全局變量和函數(shù)InsertId：函數(shù)，將strToken中的標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針；

InsertConst:函數(shù)，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。

DTB

：函數(shù)，把strToken中數(shù)字串譯成標(biāo)準(zhǔn)二進(jìn)制碼，并作為函數(shù)值返回（十進(jìn)制轉(zhuǎn)換為二進(jìn)制）現(xiàn)在是22頁(yè)\一共有93頁(yè)\編輯于星期二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)來(lái)說(shuō)，可讓它對(duì)應(yīng)一個(gè)switch語(yǔ)句或一組if...else語(yǔ)句；如下圖中的結(jié)點(diǎn)i對(duì)應(yīng)的程序段為：statei：GetChar();if(IsLetter()){....轉(zhuǎn)狀態(tài)j對(duì)應(yīng)的程序段....}elseif(IsDigit()){....轉(zhuǎn)狀態(tài)k對(duì)應(yīng)的程序段....}elseif(ch=='+'){....轉(zhuǎn)狀態(tài)L對(duì)應(yīng)的程序段....}else{....錯(cuò)誤處理....}現(xiàn)在是23頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)（2）根據(jù)狀態(tài)轉(zhuǎn)換圖編寫代碼的一般方法對(duì)含有回路的狀態(tài)結(jié)點(diǎn)來(lái)說(shuō)，可讓它對(duì)應(yīng)一個(gè)由while語(yǔ)句和if語(yǔ)句構(gòu)成的程序段；如下圖中的結(jié)點(diǎn)i對(duì)應(yīng)的程序段為：statei：GetChar();while(IsLetter()||IsDigit()){ GetChar();}....轉(zhuǎn)狀態(tài)j對(duì)應(yīng)的程序段....現(xiàn)在是24頁(yè)\一共有93頁(yè)\編輯于星期二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)的語(yǔ)句，其中code為單詞的種別編碼，value為單詞符號(hào)的屬性值，或無(wú)定義；如下圖中的結(jié)點(diǎn)i對(duì)應(yīng)的程序段為：凡帶有星號(hào)（*）的終態(tài)結(jié)點(diǎn)意味著多讀進(jìn)一個(gè)不屬于現(xiàn)行單詞符號(hào)的字符，該字符應(yīng)予退回，即必須把搜索指示器回調(diào)一個(gè)字符位置。如下圖中的結(jié)點(diǎn)i對(duì)應(yīng)的程序段為：statei：return(code,value);statei：Retract();return(code,value);現(xiàn)在是25頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)（3）詞法規(guī)則的相關(guān)約定 為方便起見(jiàn)，對(duì)詞法進(jìn)行如下約定：除標(biāo)識(shí)符、常數(shù)外，均為一符一種；關(guān)鍵字均作為保留字，不可用作用戶標(biāo)識(shí)符；設(shè)保留字表，識(shí)別出標(biāo)識(shí)符時(shí)，查該表確定是否為關(guān)鍵字；相鄰單詞之間至少存在一個(gè)界符、運(yùn)算符或空格?，F(xiàn)在是26頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)（4）舉例

編寫由以下?tīng)顟B(tài)轉(zhuǎn)換圖所描述的某簡(jiǎn)單語(yǔ)言的詞法分析程序。單詞符號(hào)種別編碼助憶符內(nèi)碼值DIM1$DIM—IF2$IF—DO3$DO—STOP4$STOP—END5$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)碼值現(xiàn)在是27頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)

intcode,value;

strToken="";

GetChar();

GetBC();

if(IsLetter())

{

while(IsLetter()orIsDigit())

{

Concat();

GetChar();

}

Retract()；

現(xiàn)在是28頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)

code=Reserve();

if(code==0)

{

value=InsertId(strToken);

return($ID,value);

}

elsereturn(code,－);

}

elseif(IsDigit())

{while(IsDigit())

{Contact();Getchar();}

Retract()；

value=InsertConst(strToken);

return($INT,value);

}現(xiàn)在是29頁(yè)\一共有93頁(yè)\編輯于星期二4、狀態(tài)轉(zhuǎn)換圖的代碼實(shí)現(xiàn)

elseif(ch=='=')return($ASSIGN,－);

elseif(ch=='+')return($PLUS,－);

elseif(ch=='*')

{GetChar();

if(ch=='*')return($POWER,－);

Retract();return($STAR,－);

}elseif(ch==';')return($SEMICOLON,-);

elseif(ch=='(')return($LPAR,-);

elseif(ch==')')return($RPAR,-);

elseProcError();//錯(cuò)誤處理；現(xiàn)在是30頁(yè)\一共有93頁(yè)\編輯于星期二實(shí)驗(yàn)一詞法分析器的設(shè)計(jì)（1）實(shí)驗(yàn)?zāi)康暮鸵罄斫庠~法分析器的任務(wù)和輸出形式；理解掃描器的工作原理；掌握狀態(tài)轉(zhuǎn)換圖的繪制以及單詞的識(shí)別技術(shù)；掌握詞法分析器的設(shè)計(jì)過(guò)程，能夠使用某種高級(jí)語(yǔ)言實(shí)現(xiàn)一個(gè)詞法分析器。（2）實(shí)驗(yàn)內(nèi)容 給出一個(gè)簡(jiǎn)單語(yǔ)言的詞法規(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)串。現(xiàn)在是31頁(yè)\一共有93頁(yè)\編輯于星期二實(shí)驗(yàn)一詞法分析器的設(shè)計(jì) 請(qǐng)完成以下任務(wù)：畫出識(shí)別該語(yǔ)言詞法規(guī)則的狀態(tài)轉(zhuǎn)換圖；依據(jù)該狀態(tài)轉(zhuǎn)換圖編制出詞法分析程序，能夠從輸入的源程序中，識(shí)別出各個(gè)具有獨(dú)立意義的單詞，即基本保留字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符五大類。并依次輸出各個(gè)單詞的內(nèi)部編碼（種別碼）及單詞符號(hào)自身值。現(xiàn)在是32頁(yè)\一共有93頁(yè)\編輯于星期二實(shí)驗(yàn)一詞法分析器的設(shè)計(jì)單詞符號(hào)種別碼內(nèi)碼單詞符號(hào)種別碼內(nèi)碼單詞符號(hào)種別碼內(nèi)碼void101*203&&216main102/204||217int103=205！218char104>206(301if105>=207)302else106<208[303for107<=209]304while108==210{305return109<>211}306cout110++212，307cin111--213；308+201>>214標(biāo)識(shí)符400-202<<215常數(shù)500二進(jìn)制形式返回現(xiàn)在是33頁(yè)\一共有93頁(yè)\編輯于星期二3.3單詞的描述工具正規(guī)文法

1正規(guī)式與正規(guī)集

2現(xiàn)在是34頁(yè)\一共有93頁(yè)\編輯于星期二1、正規(guī)文法正規(guī)文法（線性文法） 若文法G的任一產(chǎn)生式的形式都為A→aB或A→a，其中A，B∈VN

，a∈VT*，則稱G為一個(gè)右線性文法； 若文法G的任一產(chǎn)生式的形式都為A→Ba或A→a，其中A，B∈VN

，a∈VT*，則稱G為一個(gè)左線性文法。右線性文法和左線性文法統(tǒng)稱為正規(guī)文法或3型文法。【例3.2】

設(shè)有文法G1=(VT,VN,S,P)，其中VT={0,1}，VN={S,A,B}，P為：S→0A|1BA→10A|1B→01B|0則G1是一個(gè)正規(guī)文法。

返回現(xiàn)在是35頁(yè)\一共有93頁(yè)\編輯于星期二2、正規(guī)式與正規(guī)集（1）正規(guī)式與正規(guī)集的遞歸定義?和?都是∑上的正規(guī)式，它們所表示的正規(guī)集分別為{?}和?；任何ａ∈∑，ａ是∑上的正規(guī)式，它所表示的正規(guī)集為{ａ}；假定U和V都是∑上的正規(guī)式，它們所表示的正規(guī)集分別為Ｌ(U)和Ｌ(V)，那么，(U|V)、(U·V)和(U*)也都是正規(guī)式，它們所表示的正規(guī)集分別為Ｌ(U)∪Ｌ(V)、Ｌ(U)Ｌ(V)和（Ｌ(U)*）。 僅由有限次使用上述三步驟而得到的表達(dá)式才是∑上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是∑上的正規(guī)集。（2）正規(guī)式的運(yùn)算 正規(guī)式的運(yùn)算符“|”、“·”和“*”分別讀作“或”、“連接”和“閉包”。運(yùn)算符的優(yōu)先級(jí)依次由低到高。連接符“·”一般可以省略不寫?，F(xiàn)在是36頁(yè)\一共有93頁(yè)\編輯于星期二2、正規(guī)式與正規(guī)集

【例3.6】

令∑={a，b}，則∑上的正規(guī)式和相應(yīng)的正規(guī)集如下所示：正規(guī)式正規(guī)集a{a}a|b{a,b}ab{ab}(a|b)(a|b){aa,ab,ba,bb}a*{ε,a,aa,……,任意個(gè)a的串}(a|b)*{ε,a,b,aa,ab,……,所有由a和b組成的串}(a|b)*(aa|bb)(a|b)*{∑上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串}現(xiàn)在是37頁(yè)\一共有93頁(yè)\編輯于星期二2、正規(guī)式與正規(guī)集（3）正規(guī)式的等價(jià) 若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則稱這兩個(gè)正規(guī)式等價(jià)。即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ī)集現(xiàn)在是38頁(yè)\一共有93頁(yè)\編輯于星期二2、正規(guī)式與正規(guī)集（4）正規(guī)式和正規(guī)集的運(yùn)算律結(jié)合律

正規(guī)式正規(guī)集現(xiàn)在是39頁(yè)\一共有93頁(yè)\編輯于星期二2、正規(guī)式與正規(guī)集（4）正規(guī)式和正規(guī)集的運(yùn)算律分配律

正規(guī)式正規(guī)集現(xiàn)在是40頁(yè)\一共有93頁(yè)\編輯于星期二2、正規(guī)式與正規(guī)集（4）正規(guī)式和正規(guī)集的運(yùn)算律對(duì)任何正規(guī)式和正規(guī)集有：【例3.7】

證明 證明：利用正規(guī)式的分配律和結(jié)合律直接推導(dǎo)：

現(xiàn)在是41頁(yè)\一共有93頁(yè)\編輯于星期二作業(yè)3.1習(xí)題三（P64）：2(1)(2)3(1)(2)(3)返回現(xiàn)在是42頁(yè)\一共有93頁(yè)\編輯于星期二3.4有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)（DFA）

1非確定有限自動(dòng)機(jī)（NFA）

2將NFA轉(zhuǎn)換為DFA

3確定有限自動(dòng)機(jī)的化簡(jiǎn)

4現(xiàn)在是43頁(yè)\一共有93頁(yè)\編輯于星期二1、確定有限自動(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è)輸入符號(hào)，所以也稱為輸入符號(hào)字母表。δ是狀態(tài)轉(zhuǎn)換函數(shù)，是在S×∑→S上的單值映射。定義形式:δ(s，a)=s’，其中s∈S，s’∈S，表示當(dāng)現(xiàn)行狀態(tài)為s，輸入字符為a時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)s’。稱s’為s的一個(gè)后續(xù)狀態(tài)。s0∈S，是唯一的一個(gè)初態(tài)。FS，可空,是一個(gè)終態(tài)集,終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。

現(xiàn)在是44頁(yè)\一共有93頁(yè)\編輯于星期二1、確定有限自動(dòng)機(jī)（DFA）（2）表示形式狀態(tài)轉(zhuǎn)換矩陣 一個(gè)DFA可用一個(gè)矩陣表示，行表示狀態(tài)，列表示輸入字符，矩陣元素表示δ(s,a)的值。這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣?！纠?.8】DFAM=({S,U,V,Q}，{a,b}，δ，S，{Q})，其中δ定義為：

δ(S,a)=U，δ(S,b)=V，δ(U,a)=Q，δ(U,b)=Vδ(V,a)=U，δ(V,b)=Q，δ(Q,a)=Q，δ(Q,b)=Q則該DFA對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表所示。

字符狀態(tài)abSUVUQVVUQQQQ現(xiàn)在是45頁(yè)\一共有93頁(yè)\編輯于星期二1、確定有限自動(dòng)機(jī)（DFA）（2）表示形式狀態(tài)轉(zhuǎn)換圖 一個(gè)DFA可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖，假定DFAM含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)。【例3.9】例3.8中所定義的DFAM相應(yīng)的狀態(tài)轉(zhuǎn)換圖如下圖所示：

現(xiàn)在是46頁(yè)\一共有93頁(yè)\編輯于星期二1、確定有限自動(dòng)機(jī)（DFA）（3）可識(shí)別 對(duì)于Σ*中的任何字α，若存在一條從初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的路徑，這條路徑即為通路。若這條通路上所有弧的標(biāo)記符連接成的字等于α，則稱α可為DFAM所識(shí)別（或接受）。若M的初態(tài)結(jié)點(diǎn)同時(shí)也是終態(tài)結(jié)點(diǎn)，則空字可為M所識(shí)別。DFAM=（S，∑，δ，s0，F(xiàn))所能接受的字符串的全體為L(zhǎng)（M）。（4）定理 如果一個(gè)DFAM的輸入字母表為∑，則稱M是∑上的一個(gè)DFA，可以證明：∑上的一個(gè)字集V∑*是正規(guī)的，當(dāng)且僅當(dāng)存在∑上的DFAM，使得V=L（M）。

返回現(xiàn)在是47頁(yè)\一共有93頁(yè)\編輯于星期二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)。∑是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào)字母表。δ是狀態(tài)轉(zhuǎn)換函數(shù)，δ：S×∑*→2S，即δ是一個(gè)從S×Σ*到S的子集的映射（多值映射），其中，2S表示S的所有子集的全體。S0S，是一個(gè)非空的初態(tài)集合。FS，可空，是一個(gè)終態(tài)集合，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。

現(xiàn)在是48頁(yè)\一共有93頁(yè)\編輯于星期二2、非確定有限自動(dòng)機(jī)（NFA）（2）表示形式 一個(gè)NFA也可以用狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖來(lái)表示。狀態(tài)轉(zhuǎn)換矩陣的行表示狀態(tài)，列表示輸入字，矩陣元素表示δ(s，a)的值。下面，主要介紹狀態(tài)轉(zhuǎn)換圖的表示方法。NFA的狀態(tài)轉(zhuǎn)換圖表示

若一個(gè)NFAM含有m個(gè)狀態(tài)和n個(gè)輸入字符，那么它所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖就含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干條箭弧與別的結(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)。

現(xiàn)在是49頁(yè)\一共有93頁(yè)\編輯于星期二2、非確定有限自動(dòng)機(jī)（NFA）（3）可識(shí)別 對(duì)于Σ*中的任何一個(gè)字α，若存在一條從某一個(gè)初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字等于α，則稱α可為NFAM所識(shí)別（讀出或接受）。若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í)別。 例如，下圖所示的NFAM所能識(shí)別的是所有含有相繼兩個(gè)a或相繼兩個(gè)b的字。

返回現(xiàn)在是50頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA（1）NFA與DFA的等價(jià)性定理 對(duì)每一個(gè)NFAN，一定存在一個(gè)DFAM，使得：L(M)=L(N)，即對(duì)于每個(gè)NFAN存在著與之等價(jià)的DFAM，而且與某一NFA等價(jià)的DFA是不唯一的。（2）子集算法 可以通過(guò)子集法的算法來(lái)將NFA轉(zhuǎn)換成接受相同語(yǔ)言的DFA。子集法的基本思想是：把DFA中的每一個(gè)狀態(tài)對(duì)應(yīng)NFA中的一組狀態(tài)。即由于NFA中的δ是多值的，所以在讀入一個(gè)輸入符號(hào)后可能達(dá)到的狀態(tài)是集合，而子集法就是用DFA的狀態(tài)記錄該狀態(tài)的集合?，F(xiàn)在是51頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA（3）子集算法涉及的相關(guān)運(yùn)算?閉包?_CLOSURE(I) 假定I是M的狀態(tài)集的子集，定義I的?閉包?_CLOSURE(I)為：若q∈I，則q∈?_CLOSURE(I)；若q∈I，那么從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)過(guò)一條a弧而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體。 可以先通過(guò)I求J，J={y|y=δ(x,a),x∈I}，再求?_CLOSURE(J)，即得Ia?，F(xiàn)在是52頁(yè)\一共有93頁(yè)\編輯于星期二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)={5,6,2,3,8,4,7}。現(xiàn)在是53頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA（4）NFA確定化為DFA的方法

假設(shè)NFAM=（S，∑，δ，S0，F(xiàn))，可按如下方法對(duì)其確定化：對(duì)M的狀態(tài)轉(zhuǎn)換圖作如下改造：引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y。X，YS，從X到S0中任意狀態(tài)結(jié)點(diǎn)連一條?箭弧，從F中任意狀態(tài)結(jié)點(diǎn)連一條?箭弧到Y(jié)?，F(xiàn)在是54頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA（4）NFA確定化為DFA的方法對(duì)M的狀態(tài)轉(zhuǎn)換圖按下圖所示的規(guī)則作重復(fù)替換，其中K是新引入的狀態(tài)。重復(fù)這種分裂過(guò)程直至狀態(tài)轉(zhuǎn)換圖中的每條箭弧上的標(biāo)記或?yàn)?，或?yàn)椤浦械膯蝹€(gè)字母。

將完成以上操作后最終得到的NFA記為M′，顯然有：L(M′)=L(M)。現(xiàn)在是55頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA（4）NFA確定化為DFA的方法

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

根據(jù)狀態(tài)轉(zhuǎn)換表構(gòu)造狀態(tài)轉(zhuǎn)換矩陣（DFAM〞） 假設(shè)∑＝{a1,…,ak}，針對(duì)M′構(gòu)造如下的狀態(tài)轉(zhuǎn)換表：將狀態(tài)轉(zhuǎn)換表中的每個(gè)狀態(tài)子集視為新的狀態(tài)，將其作為M〞的狀態(tài)；M〞的初態(tài)是狀態(tài)轉(zhuǎn)換表中首行首列的狀態(tài)子集對(duì)應(yīng)的那個(gè)狀態(tài)；M〞的終態(tài)是狀態(tài)轉(zhuǎn)換表中含有M′終態(tài)的狀態(tài)子集對(duì)應(yīng)的那些狀態(tài)。 顯然，有L(M〞)=L(M′)=L(M)。現(xiàn)在是57頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA【例3.12】

構(gòu)造識(shí)別正規(guī)式(a|b)*(aa|bb)(a|b)*的NFA，并將其確定化為DFA。解：①構(gòu)造NFA現(xiàn)在是58頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA構(gòu)造狀態(tài)轉(zhuǎn)換表IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,4,1}{5,3,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1}{5,4,1}{5,3,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,2,6,Y}{5,4,1,6,Y}現(xiàn)在是59頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA重命名，構(gòu)造狀態(tài)轉(zhuǎn)換矩陣IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,3,1,2,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}Sab012132214335464564635其中，0為初態(tài)，3,4,5,6為終態(tài)現(xiàn)在是60頁(yè)\一共有93頁(yè)\編輯于星期二3、將NFA轉(zhuǎn)換為DFA繪制狀態(tài)轉(zhuǎn)換圖Sab012132214335464564635返回現(xiàn)在是61頁(yè)\一共有93頁(yè)\編輯于星期二4、確定有限自動(dòng)機(jī)的化簡(jiǎn)（1）DFA的化簡(jiǎn)（最小化DFA） 對(duì)于任意給定的DFAM，構(gòu)造另一個(gè)DFAM′，使得L(M)=L(M′)，且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是等價(jià)的；如果DFAM的兩個(gè)狀態(tài)s和t不等價(jià)，則稱狀態(tài)s和t是可區(qū)別的。可區(qū)別等價(jià)現(xiàn)在是62頁(yè)\一共有93頁(yè)\編輯于星期二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à)現(xiàn)在是63頁(yè)\一共有93頁(yè)\編輯于星期二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ī)的開始狀態(tài)出發(fā)，任何輸入串也不能達(dá)到的狀態(tài)，即從初態(tài)結(jié)點(diǎn)開始永遠(yuǎn)到達(dá)不了的那些狀態(tài)。（5）DFA最小化算法（子集分割算法）基本思想將DFAM中的狀態(tài)集分割成一些互不相交的子集，使得任何不同的兩個(gè)子集中的狀態(tài)都是可區(qū)別的，而同一個(gè)子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。從每個(gè)子集中任選一個(gè)狀態(tài)作為代表，同時(shí)消去其它等價(jià)狀態(tài)及其射出的弧。把那些原來(lái)到達(dá)其它等價(jià)狀態(tài)的弧改為到達(dá)相應(yīng)的代表狀態(tài)?，F(xiàn)在是64頁(yè)\一共有93頁(yè)\編輯于星期二（5）DFA最小化算法（子集分割算法）具體步驟初始分割：把狀態(tài)集S劃分為終態(tài)集和非終態(tài)集，記為其中，屬于終態(tài)集，屬于非終態(tài)集。k次分割：假定經(jīng)過(guò)k次劃分后，得到m個(gè)子集，記為

，并且屬于不同子集中的狀態(tài)都是可區(qū)別的。檢查中的每個(gè)子集，看其能否進(jìn)一步分割。令，若存在一個(gè)輸入字符a（a∈Σ），使得不全包含在現(xiàn)行分割的某一子集中，就將一分為二。4、確定有限自動(dòng)機(jī)的化簡(jiǎn)現(xiàn)在是65頁(yè)\一共有93頁(yè)\編輯于星期二分割辦法： 假設(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)q1和q2不等價(jià)t1和t2不等價(jià)現(xiàn)在是66頁(yè)\一共有93頁(yè)\編輯于星期二（5）DFA最小化算法（子集分割算法）具體步驟循環(huán)分割：重復(fù)上一步，直到子集個(gè)數(shù)不再增加為止（即每個(gè)子集已是不可再分的了）。所謂不能劃分，是指該子集或者僅有一個(gè)狀態(tài)，或者雖有多個(gè)狀態(tài)但這些狀態(tài)均不可區(qū)別（即等價(jià)）。選代表，刪除等價(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及其所射出的弧從原來(lái)的DFA中刪除。決定初態(tài)和終態(tài)：設(shè)刪除等價(jià)狀態(tài)之后的DFA為M′，凡那些包含M的初態(tài)的狀態(tài)子集所對(duì)應(yīng)的代表狀態(tài)均作為M′的初態(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)現(xiàn)在是67頁(yè)\一共有93頁(yè)\編輯于星期二4、確定有限自動(dòng)機(jī)的化簡(jiǎn)【例3.13】

對(duì)下圖所示的DFAM進(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}。現(xiàn)在是68頁(yè)\一共有93頁(yè)\編輯于星期二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}。現(xiàn)在是69頁(yè)\一共有93頁(yè)\編輯于星期二4、確定有限自動(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ū)別的?，F(xiàn)在是70頁(yè)\一共有93頁(yè)\編輯于星期二4、確定有限自動(dòng)機(jī)的化簡(jiǎn)

⑤選代表，刪除多余狀態(tài) 令狀態(tài)3代表{3，4，5，6}，把原來(lái)導(dǎo)入4，5，6的弧全都導(dǎo)入3，并刪除4，5，6，最后可得下圖所示的最小化DFA?，F(xiàn)在是71頁(yè)\一共有93頁(yè)\編輯于星期二作業(yè)3.2習(xí)題三（P64）：56(1)(2)返回現(xiàn)在是72頁(yè)\一共有93頁(yè)\編輯于星期二3.5正規(guī)文法、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)特性正規(guī)文法與正規(guī)式的等價(jià)性

1正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性

2正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性

3總結(jié)

4現(xiàn)在是73頁(yè)\一共有93頁(yè)\編輯于星期二1、正規(guī)文法與正規(guī)式的等價(jià)性

一個(gè)正規(guī)語(yǔ)言（正規(guī)集）既可以用正規(guī)文法定義，也可以用正規(guī)式定義。關(guān)于正規(guī)文法和正規(guī)式有以下等價(jià)性定理：（1）定理對(duì)任何正規(guī)式r，都存在一個(gè)正規(guī)文法G，使得L(G)=L(r)。對(duì)任何正規(guī)文法G，都存在一個(gè)正規(guī)式r，使得L(r)=L(G)?，F(xiàn)在是74頁(yè)\一共有93頁(yè)\編輯于星期二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（S∈VN）作為G的開始符號(hào)，并生成初始產(chǎn)生式S→r。然后，對(duì)該產(chǎn)生式反復(fù)運(yùn)用下述規(guī)則進(jìn)行變換，直到所生成的每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符為止。假設(shè)x和y都是正規(guī)式：規(guī)則1：形如A→xy，變換為A→xB，B→y，B∈VN；規(guī)則2：形如A→x*y，變換為A→xA,A→y；規(guī)則3：形如A→x|y，變換為A→x,A→y。現(xiàn)在是75頁(yè)\一共有93頁(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，首先形成S→a(a|d)*，然后做變換：最后，得到的正規(guī)文法G的產(chǎn)生式為：VN={S,A}。現(xiàn)在是76頁(yè)\一共有93頁(yè)\編輯于星期二1、正規(guī)文法與正規(guī)式的等價(jià)性（3）正規(guī)文法到正規(guī)式的轉(zhuǎn)換 可按如下方法將正規(guī)文法G=（VT，VN，S，P）轉(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：形如A→xB，B→y，變換為A→xy；規(guī)則2：形如A→xA,A→y，變換為A→x*y；規(guī)則3：形如A→x,A→y，變換為A→x|y?，F(xiàn)在是77頁(yè)\一共有93頁(yè)\編輯于星期二1、正規(guī)文法與正規(guī)式的等價(jià)性

【例3.16】

有正規(guī)文法G[S]，其中的產(chǎn)生式為：S→dA|eB，A→aA|b，B→bB|c，將該文法G轉(zhuǎn)換成正規(guī)式。解：令∑={a,b,c,d,e}，然后對(duì)文法G[S]中的產(chǎn)生式做如下變換：將A，B代入S產(chǎn)生式的右部，得那么，與正規(guī)文法G[S]等價(jià)的正規(guī)式為：返回現(xiàn)在是78頁(yè)\一共有93頁(yè)\編輯于星期二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是等價(jià)的。關(guān)于正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性，有以下結(jié)論：對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)(FA)M，使得L(M)＝L(G)。對(duì)每一個(gè)FAM，都存在一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL，使得L(M)＝L(GR)＝L(GL)?，F(xiàn)在是79頁(yè)\一共有93頁(yè)\編輯于星期二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)造方法如下：M的字母表與G的終結(jié)符集合相同，即∑=VT；讓G中的每個(gè)非終結(jié)符對(duì)應(yīng)M中的一個(gè)狀態(tài)結(jié)點(diǎn)；以G的開始符作為M的初態(tài)結(jié)點(diǎn)，即S0=S；引進(jìn)一個(gè)新的終態(tài)結(jié)點(diǎn)f，即S=VN∪{f}；對(duì)G中形如A→aB的產(chǎn)生式，則令δ(A,a)=B；對(duì)G中形如A→a的產(chǎn)生式，則令δ(A,a)=f?，F(xiàn)在是80頁(yè)\一共有93頁(yè)\編輯于星期二2、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性【例3.17】

設(shè)有右線性正規(guī)文法G=({0,1},{A,B,C,D},A,P)，其中P為：

A→0|0B|1DB→0D|1C

C→0|0B|1DD→0D|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,0)=B，δ(C,1)=D，δ(D,0)=D，δ(D,1)=D其狀態(tài)轉(zhuǎn)換圖如下圖所示：現(xiàn)在是81頁(yè)\一共有93頁(yè)\編輯于星期二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)造方法如下：M的字母表與G的