編譯原理清華大學(xué)第4章 詞法分析

1、武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌【課前思考】【課前思考】1 C語言，語言，PASCAL語言的程序是由什么組成的？語言的程序是由什么組成的？2 C語言，語言，PASCAL語言的標(biāo)識(shí)符語言的標(biāo)識(shí)符(變量變量)和數(shù)的表示分和數(shù)的表示分別有什么規(guī)定？別有什么規(guī)定？3 詞法分析是什么詞法分析是什么? 詞法分析程序的功能是什么？詞法分析程序的功能是什么？4 編寫一個(gè)程序（采用編寫一個(gè)程序（采用C或或PASCAL語言）識(shí)別語言）識(shí)別C語言語言的標(biāo)識(shí)符。的標(biāo)識(shí)符。 5 PL/0詞法分析程序識(shí)別哪幾種單詞？詞法分析程序識(shí)別哪幾種單詞？武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科

2、學(xué)系陳天煌【學(xué)習(xí)目標(biāo)】【學(xué)習(xí)目標(biāo)】1 明確詞法分析在編譯過程所處的階段和作用。明確詞法分析在編譯過程所處的階段和作用。2 理解通常的單詞分類和構(gòu)詞規(guī)則。理解通常的單詞分類和構(gòu)詞規(guī)則。3 掌握詞法分析程序的手工實(shí)現(xiàn)方法。掌握詞法分析程序的手工實(shí)現(xiàn)方法。4 學(xué)會(huì)使用單詞的描述和識(shí)別工具學(xué)會(huì)使用單詞的描述和識(shí)別工具-正則表達(dá)正則表達(dá)式和自動(dòng)機(jī)。式和自動(dòng)機(jī)。5 掌握詞法分析程序的自動(dòng)構(gòu)造原理。掌握詞法分析程序的自動(dòng)構(gòu)造原理。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌【學(xué)習(xí)指南】【學(xué)習(xí)指南】 詞法分析程序是編譯程序的一個(gè)構(gòu)成成分，它的主要任務(wù)是掃描源程序，按構(gòu)詞規(guī)則識(shí)別單詞，并報(bào)告發(fā)現(xiàn)

3、的詞法錯(cuò)誤。詞法分析也是語法分析的一部分，把詞法分析從語法分析中獨(dú)立出來是為了使編譯程序結(jié)構(gòu)清晰，也是為了便于使用自動(dòng)構(gòu)造工具，提高編譯效率。 本章首先介紹詞法分析程序的功能和設(shè)計(jì)原則，然后引入正規(guī)式和其對單詞的描述，接著講述有窮自動(dòng)機(jī)理論，最后給出詞法分析程序的自動(dòng)構(gòu)造原理。7 如何確定一個(gè)輸入符號(hào)串是否是所給文法的句子？如何確定一個(gè)輸入符號(hào)串是否是所給文法的句子？武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌第第4 4章章 詞法分析詞法分析 本章將討論詞法分析程序的設(shè)計(jì)原則，本章將討論詞法分析程序的設(shè)計(jì)原則，單詞的描述技術(shù)，識(shí)別機(jī)制及詞法分析單詞的描述技術(shù)，識(shí)別機(jī)制及詞法分析

4、程序的自動(dòng)構(gòu)造原理。程序的自動(dòng)構(gòu)造原理。4.1 對于詞法分析程序的要求對于詞法分析程序的要求4.2 正規(guī)表達(dá)式與正規(guī)集（正規(guī)語言）正規(guī)表達(dá)式與正規(guī)集（正規(guī)語言）4.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)4.5 正規(guī)文法與有窮自動(dòng)機(jī)的等價(jià)性正規(guī)文法與有窮自動(dòng)機(jī)的等價(jià)性4.4 正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性4.6 詞法分析程序的構(gòu)造詞法分析程序的構(gòu)造武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌本章重點(diǎn)本章重點(diǎn) 單詞的描述工具單詞的描述工具 單詞的識(shí)別系統(tǒng)單詞的識(shí)別系統(tǒng) 設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序首先需要描述和刻畫程序設(shè)計(jì)語言中的首先需要描述和刻畫程序設(shè)計(jì)語

5、言中的原子單位原子單位單詞，其次需要識(shí)別單詞單詞，其次需要識(shí)別單詞和執(zhí)行某些相關(guān)的動(dòng)作和執(zhí)行某些相關(guān)的動(dòng)作。描述程序設(shè)計(jì)語言的詞法的機(jī)制是正則描述程序設(shè)計(jì)語言的詞法的機(jī)制是正則表達(dá)式，識(shí)別機(jī)制是有窮狀態(tài)自動(dòng)機(jī)。表達(dá)式，識(shí)別機(jī)制是有窮狀態(tài)自動(dòng)機(jī)。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌詞法分析程序詞法分析程序 實(shí)現(xiàn)詞法分析（實(shí)現(xiàn)詞法分析（lexical analysislexical analysis）的程）的程序稱為詞法分析程序（或掃描器）。序稱為詞法分析程序（或掃描器）。對構(gòu)成源程序的字符串從左到右的掃描，對構(gòu)成源程序的字符串從左到右的掃描，逐個(gè)字符地讀入源程序字符并按照

6、構(gòu)詞規(guī)則逐個(gè)字符地讀入源程序字符并按照構(gòu)詞規(guī)則切分成一個(gè)一個(gè)具有獨(dú)立意義的單詞。并確切分成一個(gè)一個(gè)具有獨(dú)立意義的單詞。并確定其屬性（如保留字、標(biāo)識(shí)符、運(yùn)算符、界定其屬性（如保留字、標(biāo)識(shí)符、運(yùn)算符、界限符和常量等）。再把它們轉(zhuǎn)換成長度統(tǒng)一限符和常量等）。再把它們轉(zhuǎn)換成長度統(tǒng)一的標(biāo)準(zhǔn)形式的標(biāo)準(zhǔn)形式屬性字（屬性字（TOKENTOKEN）。）。詞法分析程序的主要任務(wù)：詞法分析程序的主要任務(wù)：武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 詞法分析是編譯過程中的第一個(gè)階段，詞法分析是編譯過程中的第一個(gè)階段，在語法分析前進(jìn)行在語法分析前進(jìn)行 。也可以和語法分析結(jié)。也可以和語法分析結(jié)合在一起作

7、為一遍，由語法分析程序調(diào)用合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析詞法分析程序來獲得當(dāng)前單詞供語法分析使用。使用。源程序源程序詞法分析程序詞法分析程序語法分析程序語法分析程序Tokenget token. .詞法分析程序和語法分析程序的關(guān)系詞法分析程序和語法分析程序的關(guān)系武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 詞法分析工作從語法分析工作獨(dú)立出詞法分析工作從語法分析工作獨(dú)立出來的原因：來的原因：簡化設(shè)計(jì)簡化設(shè)計(jì)改進(jìn)編譯效率改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性增加編譯系統(tǒng)的可移植性武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 4.

8、1 4.1 對于詞法分析器的要求對于詞法分析器的要求4.1.1 4.1.1 詞法分析器的功能和輸出形式詞法分析器的功能和輸出形式功能：輸入源程序，輸出單詞符號(hào)。功能：輸入源程序，輸出單詞符號(hào)。 單詞符號(hào)是一個(gè)程序語言的基本語法符號(hào)。單詞符號(hào)是一個(gè)程序語言的基本語法符號(hào)。單詞的分類（五類）：單詞的分類（五類）：(1) 關(guān)鍵字：關(guān)鍵字：由程序語言定義的具有固定意義的標(biāo)由程序語言定義的具有固定意義的標(biāo) 識(shí)識(shí) 符。也稱為保留字或基本字。符。也稱為保留字或基本字。(2) 標(biāo)識(shí)符：標(biāo)識(shí)符：用來表示程序中各種名字的字符串。用來表示程序中各種名字的字符串。(3) 常常 數(shù)：數(shù)：常數(shù)的類型一般有整型、實(shí)型、布爾

9、型、常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型。文字型。(4) 運(yùn)算符：運(yùn)算符：如如+、 、*、/ 等。等。(5) 界限符：界限符：如逗號(hào)、分號(hào)、括號(hào)等。如逗號(hào)、分號(hào)、括號(hào)等。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 一個(gè)程序語言的關(guān)鍵字、運(yùn)算符、界限符都是固一個(gè)程序語言的關(guān)鍵字、運(yùn)算符、界限符都是固定的，即數(shù)量有限及意義明確；而對于標(biāo)識(shí)符和常數(shù)通定的，即數(shù)量有限及意義明確；而對于標(biāo)識(shí)符和常數(shù)通常是不確定的。常是不確定的。 詞法分析器所輸出的單詞符號(hào)常常表示成如詞法分析器所輸出的單詞符號(hào)常常表示成如下的二元式：下的二元式： （單詞種別，單詞符號(hào)的屬性值）（單詞種別，單詞符號(hào)

10、的屬性值） 單詞種別通常用整數(shù)編碼。一個(gè)語言的單詞符號(hào)如何分單詞種別通常用整數(shù)編碼。一個(gè)語言的單詞符號(hào)如何分種，分成幾種，怎樣編碼，是一個(gè)技術(shù)性的問題。它主要取種，分成幾種，怎樣編碼，是一個(gè)技術(shù)性的問題。它主要取決于處理上的方便。標(biāo)識(shí)符一般統(tǒng)歸為一種。常數(shù)則直按類決于處理上的方便。標(biāo)識(shí)符一般統(tǒng)歸為一種。常數(shù)則直按類型（整、實(shí)、布爾等）分種。關(guān)鍵字可將其全體視為一種，型（整、實(shí)、布爾等）分種。關(guān)鍵字可將其全體視為一種，也可以一字一種。采用一字一種的分法實(shí)際處理起來較為方也可以一字一種。采用一字一種的分法實(shí)際處理起來較為方便。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共便。運(yùn)算符可采用一符一種

11、的分法，但也可以把具有一定共性的運(yùn)算符視為一種。至于界符一般用一符一種的分法。性的運(yùn)算符視為一種。至于界符一般用一符一種的分法。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 如果一個(gè)種別只含一個(gè)單詞符號(hào)，那么，如果一個(gè)種別只含一個(gè)單詞符號(hào)，那么，對于這個(gè)單詞符號(hào)，種別編碼就完全代表它對于這個(gè)單詞符號(hào)，種別編碼就完全代表它自身了。若一個(gè)種別含有多個(gè)單詞符號(hào)，那自身了。若一個(gè)種別含有多個(gè)單詞符號(hào)，那么，對于它的每個(gè)單詞符號(hào)，除了給出種別么，對于它的每個(gè)單詞符號(hào)，除了給出種別編碼之外，還應(yīng)給出有關(guān)單詞符號(hào)的屬性信編碼之外，還應(yīng)給出有關(guān)單詞符號(hào)的屬性信息。息。 單詞符號(hào)的屬性是指單詞符

12、號(hào)的特性或單詞符號(hào)的屬性是指單詞符號(hào)的特性或特征。屬性值則是反應(yīng)特性或特征的值。例特征。屬性值則是反應(yīng)特性或特征的值。例如，對于某個(gè)標(biāo)識(shí)符，常將存放它的有關(guān)信如，對于某個(gè)標(biāo)識(shí)符，常將存放它的有關(guān)信息的符號(hào)表項(xiàng)的指針作為其屬性值；對于某息的符號(hào)表項(xiàng)的指針作為其屬性值；對于某個(gè)常數(shù)，則將存放它的常數(shù)表項(xiàng)的指針作為個(gè)常數(shù)，則將存放它的常數(shù)表項(xiàng)的指針作為其屬性值。其屬性值。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 在教材中，我們假定關(guān)鍵字、運(yùn)算符和界限在教材中，我們假定關(guān)鍵字、運(yùn)算符和界限符都是一符一種。對于它們，詞法分析器只給出符都是一符一種。對于它們，詞法分析器只給出其種別編碼

13、，不給出它自身的值。標(biāo)識(shí)符單列一其種別編碼，不給出它自身的值。標(biāo)識(shí)符單列一種。常數(shù)按類型分種。種。常數(shù)按類型分種。考慮下述考慮下述C十代碼段：十代碼段： while（ij）i； 經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號(hào)序列：單詞符號(hào)序列： while， （，（， id，指向，指向i的符號(hào)表項(xiàng)的指針的符號(hào)表項(xiàng)的指針 ， id，指向，指向j的符號(hào)表項(xiàng)的指針的符號(hào)表項(xiàng)的指針 ），）， id，指向，指向i的符號(hào)表項(xiàng)的指針的符號(hào)表項(xiàng)的指針 ， ；，；，武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌4.1.24.1.2詞法分析器的設(shè)計(jì)詞法分析器的設(shè)

14、計(jì) 我們將按照詞法分析的任務(wù)和作為一個(gè)獨(dú)我們將按照詞法分析的任務(wù)和作為一個(gè)獨(dú)立子程序的要求來考慮詞法分析器的設(shè)計(jì)。立子程序的要求來考慮詞法分析器的設(shè)計(jì)。一、一、 輸入、預(yù)處理輸入、預(yù)處理 詞法分析器工作的第一步是輸入源程序文詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個(gè)緩沖區(qū)中，這個(gè)緩本。輸入串一般是放在一個(gè)緩沖區(qū)中，這個(gè)緩沖區(qū)稱輸入緩沖區(qū)。詞法分析的工作（單詞符沖區(qū)稱輸入緩沖區(qū)。詞法分析的工作（單詞符號(hào)的識(shí)別）可以直接在這個(gè)緩沖區(qū)中進(jìn)行。但號(hào)的識(shí)別）可以直接在這個(gè)緩沖區(qū)中進(jìn)行。但在許多情況下，把輸入串預(yù)處理一下，對單詞在許多情況下，把輸入串預(yù)處理一下，對單詞符號(hào)的識(shí)別工作將是比

15、較方便的。符號(hào)的識(shí)別工作將是比較方便的。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 某些跳格符、回車符和換行符等編輯性字符，在某些跳格符、回車符和換行符等編輯性字符，在別處的任何出現(xiàn)都沒有意義，預(yù)處理時(shí)可以將其別處的任何出現(xiàn)都沒有意義，預(yù)處理時(shí)可以將其剔掉。剔掉。 注解部分注解部分僅在于改善程序的易讀性和易理解性。僅在于改善程序的易讀性和易理解性。對于它們，預(yù)處理時(shí)可以將其剔掉。對于它們，預(yù)處理時(shí)可以將其剔掉。 空白符（一個(gè)或相繼數(shù)個(gè)）用作單詞符號(hào)之間的空白符（一個(gè)或相繼數(shù)個(gè)）用作單詞符號(hào)之間的間隔，即用作界符。在這種情況下，預(yù)處理時(shí)可間隔，即用作界符。在這種情況下，預(yù)處理時(shí)

16、可把相繼的若干個(gè)空白結(jié)合成一個(gè)。把相繼的若干個(gè)空白結(jié)合成一個(gè)。 我們可以構(gòu)造一個(gè)預(yù)處理子程序，它能夠完我們可以構(gòu)造一個(gè)預(yù)處理子程序，它能夠完成上面所述的任務(wù)。成上面所述的任務(wù)。預(yù)處理的主要工作：預(yù)處理的主要工作：武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌二、二、 單詞符號(hào)的識(shí)別：超前搜索單詞符號(hào)的識(shí)別：超前搜索 詞法分析器的結(jié)構(gòu)如圖詞法分析器的結(jié)構(gòu)如圖4.14.1所示。所示。圖圖4.1 詞法分析器詞法分析器武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌三、三、 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。在狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中

17、，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用圖中，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結(jié)。箭弧上的標(biāo)記（字符）代表在射出結(jié)箭弧連結(jié)。箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)（即箭弧始結(jié)點(diǎn)）狀態(tài)下可能出現(xiàn)的輸入字符點(diǎn)（即箭弧始結(jié)點(diǎn)）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。例如，圖或字符類。例如，圖4.2（a）表示：在狀態(tài)）表示：在狀態(tài)1下，下，若輸入字符為若輸入字符為X，則讀進(jìn)，則讀進(jìn)X，并轉(zhuǎn)換到狀態(tài)，并轉(zhuǎn)換到狀態(tài)2。若。若輸入字符為輸入字符為Y，則讀進(jìn)，則讀進(jìn)Y，并轉(zhuǎn)換到狀態(tài)，并轉(zhuǎn)換到狀態(tài)3。一張。一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其中有一個(gè)被認(rèn)為是中有

18、一個(gè)被認(rèn)為是初態(tài)初態(tài)，而且實(shí)際上至少要有一，而且實(shí)際上至少要有一個(gè)個(gè)終態(tài)終態(tài)（用雙圈表示）。（用雙圈表示）。123XY圖圖4.2（a）轉(zhuǎn)換圖示例）轉(zhuǎn)換圖示例武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別（或接受一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別（或接受)一定的一定的字符串。字符串。 例如，識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖如圖例如，識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖如圖4.2（b）所示。）所示。圖圖4.24.2（b b）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌圖圖4.24.2（c c）識(shí)別整數(shù)的轉(zhuǎn)換圖識(shí)別整數(shù)的轉(zhuǎn)換圖圖圖4.24.2（d

19、d）識(shí)別識(shí)別FORTRAN實(shí)型常數(shù)的轉(zhuǎn)換圖實(shí)型常數(shù)的轉(zhuǎn)換圖武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌4.2 4.2 正規(guī)表達(dá)式與正規(guī)集（正規(guī)語言）正規(guī)表達(dá)式與正規(guī)集（正規(guī)語言） 程序設(shè)計(jì)語言中的單詞是基本語法程序設(shè)計(jì)語言中的單詞是基本語法成分。單詞符號(hào)的語法可以用有效的工成分。單詞符號(hào)的語法可以用有效的工具加以描述，并且基于這類描述工具，具加以描述，并且基于這類描述工具，實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造。實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造。 正規(guī)表達(dá)式是典型的詞法規(guī)則描述正規(guī)表達(dá)式是典型的詞法規(guī)則描述工具。工具。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌正規(guī)式正規(guī)式定義定

20、義（正規(guī)式和它所表示的正規(guī)集）：（正規(guī)式和它所表示的正規(guī)集）： 設(shè)字母表為設(shè)字母表為 ， 輔助字母表輔助字母表 = ， ， ， ， ， ， ， 正規(guī)式也稱正則表達(dá)式。正規(guī)式也稱正則表達(dá)式。 正規(guī)表達(dá)式（正規(guī)表達(dá)式（regular expression）是說明單詞的）是說明單詞的模式模式(pattern)的一種重要的表示法（記號(hào)），是定義的一種重要的表示法（記號(hào)），是定義正規(guī)集的數(shù)學(xué)工具。我們用以描述單詞符號(hào)。下面正規(guī)集的數(shù)學(xué)工具。我們用以描述單詞符號(hào)。下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。是正規(guī)式和它所表示的正規(guī)集的遞歸定義。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌1.

21、 和和 都是都是 上的正規(guī)式，它們所表示的正規(guī)上的正規(guī)式，它們所表示的正規(guī)集分別為集分別為 和和 ； 2. 對任何對任何a ，a是是 上的一個(gè)正規(guī)式，它所表上的一個(gè)正規(guī)式，它所表示的正規(guī)集為示的正規(guī)集為a；3. 假定假定e1和和e2都是都是 上的正規(guī)式，它們所表示的上的正規(guī)式，它們所表示的正規(guī)集分別為正規(guī)集分別為L(e1)和和L(e2)，那么，那么，(e1), e1 e2, e1 e2, e1 也都是正規(guī)式也都是正規(guī)式, 它們所表示的正規(guī)集分它們所表示的正規(guī)集分別為別為L(e1), L(e1) L(e2), L(e1)L(e2)和和(L(e1) 。4. 僅由有限次使用上述三步驟而定義的表達(dá)式僅

22、由有限次使用上述三步驟而定義的表達(dá)式才是才是 上的上的正規(guī)式正規(guī)式，僅由這些正規(guī)式所表示的，僅由這些正規(guī)式所表示的集合才是集合才是 上的上的正規(guī)集正規(guī)集。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌注意注意:其中其中“ ”、 “ ”、 “ ”均為均為正規(guī)式正規(guī)式運(yùn)算符：運(yùn)算符：2. “ ”讀為讀為“連接連接”；3. “ ”讀為讀為“閉包閉包”（即，任意有限次的自重（即，任意有限次的自重復(fù)連接）。復(fù)連接）。 在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符的優(yōu)先順序?yàn)榈膬?yōu)先順序?yàn)椤?”、“ ”、“ ” 。連接符。連接符“ ”一般可省略不寫。一般可省略不寫。

23、“ ”、“ ”和和“ ” 都是左結(jié)合的。都是左結(jié)合的。1. “ ”讀為讀為“或或” ；武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌例子例子令令 =a，b， 上的正規(guī)式和相應(yīng)的正規(guī)上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：集的例子有：正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 a a a b a,b ab ab (a b)(a b) aa,ab,ba,bb a ,a,a, 任意個(gè)任意個(gè)a的串的串武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌正規(guī)式正規(guī)式 正規(guī)集正規(guī)集(a b) ,a,b,aa,ab 所有由所有由a 和和b組成的串組成的串(a b) (aa bb)(a b) 上所有含有兩個(gè)相

24、繼上所有含有兩個(gè)相繼 的的a或兩個(gè)相繼的或兩個(gè)相繼的b組成組成 的串的串武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌討論下面兩個(gè)例子討論下面兩個(gè)例子例例4.2 有有 =d=d，. .，e e，+ +，-,-,則則 上的正規(guī)式上的正規(guī)式 d d (.dd (.dd )(e(+ )(e(+ - -)dd)dd ) )表示的是無符號(hào)數(shù)表示的是無符號(hào)數(shù)的集合。其中的集合。其中d d為為0 09 9的數(shù)字。的數(shù)字。結(jié)論：結(jié)論：程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義。程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義。例例4.1 令令 =l，d，則，則 上的正規(guī)式上的正規(guī)式 r=l (l d) 定定 義義

25、的正規(guī)集為的正規(guī)集為: l, l l, l d, l d d,其中其中l(wèi)代表字母代表字母,d代表數(shù)字代表數(shù)字,正規(guī)式正規(guī)式 即是即是 字母字母(字母字母 數(shù)字?jǐn)?shù)字) ,它表示的它表示的正規(guī)集中的每個(gè)元素的模式是正規(guī)集中的每個(gè)元素的模式是“以字母打頭的字母以字母打頭的字母數(shù)字串?dāng)?shù)字串”,就是就是Pascal和多數(shù)程序設(shè)計(jì)語言允許的的和多數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識(shí)符的詞法規(guī)則。標(biāo)識(shí)符的詞法規(guī)則。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌正規(guī)式的等價(jià)性正規(guī)式的等價(jià)性若兩個(gè)正規(guī)式若兩個(gè)正規(guī)式e1和和e2所表示的正規(guī)集所表示的正規(guī)集相同相同,則說則說e1和和e2等價(jià)等價(jià),寫作寫作e1=

26、e2。例如：例如： e1= (a b)， e2 = b a， e1= e2 又如：又如： e1= b(ab) , e2 =(ba) b， e1= e2 e1= (a b) , e2 =(a b ) ， e1= e2武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌設(shè)設(shè)U,V,W為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1. U V=V U “或或”服從交換律服從交換律2. U (V W)=(U V) W“或或”的可結(jié)合律的可結(jié)合律3. (UV)W=U(VW)“連接連接”的可結(jié)合律的可結(jié)合律4. U(V W)=UV UW (V W)U=VU WU分配律分配律5

27、. U=U, U =U 是是“連接連接”的恒等元的恒等元 6. U U=UU =U UU “或或”的抽取律的抽取律武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌4.3 4.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī)也稱有限自動(dòng)機(jī))作為一種識(shí)別裝作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自定義的語言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。尋找特殊的方法和工具。 有窮自動(dòng)機(jī)

28、分為兩類：確定的有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)(Deterministic Finite Automata)和不確定的有窮自和不確定的有窮自動(dòng)機(jī)動(dòng)機(jī)(Nondeterministic Finite Automata) 。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌關(guān)于關(guān)于有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)討論如下內(nèi)容：討論如下內(nèi)容： 確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DFA 不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)NFA NFA的確定化的確定化 DFA的最小化的最小化武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌1. K1. K是一個(gè)有窮狀態(tài)集，它的每個(gè)元素稱為一個(gè)狀

29、態(tài)；是一個(gè)有窮狀態(tài)集，它的每個(gè)元素稱為一個(gè)狀態(tài)；4.3.1 4.3.1 確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DFADFA 一、一、DFADFA定義：定義： 一個(gè)確定的有窮自動(dòng)機(jī)（一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：是一個(gè)五元組：M=（K，f，s0 ，Z）, ,其中其中: :2. . 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱所以也稱為輸入符號(hào)表；為輸入符號(hào)表；3. . f是轉(zhuǎn)換函數(shù)，是在是轉(zhuǎn)換函數(shù)，是在KK上的單值部分映射。即，如果上的單值部分映射。即，如果 f（ki，a）=kj，（，（kiK，kjK）就意味著，當(dāng)前狀態(tài)為就意

30、味著，當(dāng)前狀態(tài)為ki，輸入符為輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把，我們把kj稱作稱作ki的一個(gè)的一個(gè)后繼狀態(tài)；后繼狀態(tài)；5. . Z K是一個(gè)終態(tài)集是一個(gè)終態(tài)集（可空）（可空），終態(tài)也稱可接受狀態(tài)或結(jié)，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。束狀態(tài)。4. s0 KK是唯一的一個(gè)初態(tài)；是唯一的一個(gè)初態(tài)；武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌二、一個(gè)二、一個(gè)DFA DFA 的例子：的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中其中f定義為：定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q

31、，a）=Qf（U，b）=V f（Q，b）=Q武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 顯然，一個(gè)顯然，一個(gè)DFA可用一個(gè)矩陣表示，可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字該矩陣的行表示狀態(tài)，列表示輸入字符，即符，即k行行a列的列的 矩陣元素表示矩陣元素表示f（k，a）的值。這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。的值。這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。狀態(tài)狀態(tài)ab SUVUQVVUQ- - QQQ對于上例，有如下狀態(tài)轉(zhuǎn)換矩陣對于上例，有如下狀態(tài)轉(zhuǎn)換矩陣注意：在狀態(tài)矩陣中注意：在狀態(tài)矩陣中 初態(tài)結(jié)點(diǎn)的旁邊標(biāo)以初態(tài)結(jié)點(diǎn)的旁邊標(biāo)以 ；終態(tài)結(jié)點(diǎn)旁邊標(biāo)終態(tài)結(jié)點(diǎn)旁邊標(biāo) 。f（S，a）=Uf（V，a

32、）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 一個(gè)一個(gè)DFADFA也可表示成一張（確定的）狀態(tài)也可表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。轉(zhuǎn)換圖。注意：初態(tài)結(jié)點(diǎn)的旁邊標(biāo)以注意：初態(tài)結(jié)點(diǎn)的旁邊標(biāo)以 ； 終態(tài)結(jié)點(diǎn)則用雙圈表示。終態(tài)結(jié)點(diǎn)則用雙圈表示。 假定假定DFA M含有含有 m個(gè)狀態(tài)和個(gè)狀態(tài)和 n個(gè)輸入字符，個(gè)輸入字符，那么，這個(gè)圖含有那么，這個(gè)圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂多有多有n條箭弧射出和別的結(jié)點(diǎn)相連接，每條箭條箭弧射出和別的結(jié)點(diǎn)相連接，每條箭弧用弧用中的一

33、個(gè)不同輸入字符作標(biāo)記，整張圖中的一個(gè)不同輸入字符作標(biāo)記，整張圖含有唯一的一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)（可以是含有唯一的一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)（可以是0個(gè)）個(gè)）終態(tài)結(jié)點(diǎn)。終態(tài)結(jié)點(diǎn)。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌SUQVaabbbaa,b狀態(tài)狀態(tài)ab SUVUQVVUQ QQQ 對于對于* *中的任何字中的任何字，若存在一條從初態(tài)結(jié)點(diǎn)到某一終，若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字符態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字符串等于串等于，則稱，則稱可為可為DFA M所所識(shí)別識(shí)別（讀出讀出或或接受接受）。若）。若M的初態(tài)結(jié)點(diǎn)同時(shí)又

34、是終態(tài)結(jié)點(diǎn)，則空字的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字可為可為M所識(shí)別（或接所識(shí)別（或接受）受）DFA M所能識(shí)別的字的全體記為所能識(shí)別的字的全體記為L(M) 。 如有如有 =abb，顯然，顯然可為上例的可為上例的DFA M所所識(shí)別識(shí)別。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 如果一個(gè)如果一個(gè)DFA M的輸入字母表為的輸入字母表為，則我們也稱則我們也稱M是是的一個(gè)的一個(gè)DFA。換言之換言之： 若若t* ，f (S，t) =P，其中，其中S為為DFA M的的初態(tài)，初態(tài)，PZ，Z為終態(tài)集。則稱為終態(tài)集。則稱t 可為可為DFA M所接受（所接受（識(shí)別識(shí)別）。）。結(jié)論：結(jié)論：上的一

35、個(gè)字集上的一個(gè)字集V *是正規(guī)的，是正規(guī)的，當(dāng)且僅當(dāng)存在當(dāng)且僅當(dāng)存在上的上的DFA M，使得，使得VL（ M）。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌*上的符號(hào)串上的符號(hào)串t 在在DFA M上運(yùn)行上運(yùn)行:一個(gè)輸入符號(hào)串一個(gè)輸入符號(hào)串t，（將它表示成，（將它表示成T t1的形式，其的形式，其中中T， t1 *）在）在DFA M=（K，f，S，Z）上運(yùn)行的定義為：）上運(yùn)行的定義為：f（Q， Tt1）=f（f（Q，T），），t1）,其中其中QK;擴(kuò)充轉(zhuǎn)換函數(shù)擴(kuò)充轉(zhuǎn)換函數(shù)f 為為 K*K上的映射，且：上的映射，且： f（ki， ）= ki 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大

36、學(xué)計(jì)算機(jī)科學(xué)系陳天煌例：證明例：證明t=baab被下圖的被下圖的DFA所接受所接受。 bSUVQabbb,aaaf（S，baab）=f（f（S，b )，aab） = f（V，aab）= f（ f（V，a），ab） = f（U，ab）=f （ f（U，a），b） = f（Q，b）=QQ屬于終態(tài)。屬于終態(tài)。 得證。得證。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌三、三、DFADFA的確定性表現(xiàn)兩個(gè)方面：的確定性表現(xiàn)兩個(gè)方面：1. 1. 映射映射f：KK是一個(gè)單值函數(shù)。也就是說，是一個(gè)單值函數(shù)。也就是說，對任何狀態(tài)對任何狀態(tài)sK和輸入符號(hào)和輸入符號(hào)a a，f（s，a）唯一唯一地確定

37、了下一狀態(tài)。從轉(zhuǎn)換圖的角度來看，假定字地確定了下一狀態(tài)。從轉(zhuǎn)換圖的角度來看，假定字母表母表含有含有n n個(gè)輸入字符，那么，任何一個(gè)狀態(tài)結(jié)個(gè)輸入字符，那么，任何一個(gè)狀態(tài)結(jié)最多只有最多只有n n條弧射出，而且每條弧以一個(gè)不同的輸條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。入字符標(biāo)記。 2. 2. DFA有且僅有唯一的一個(gè)初態(tài)有且僅有唯一的一個(gè)初態(tài)s0K 。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌4.3.2 4.3.2 非確定的有窮自動(dòng)機(jī)非確定的有窮自動(dòng)機(jī)NFANFA1. K. K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2. . 是一個(gè)有

38、窮字母表，它的每個(gè)元素稱為一個(gè)輸入符是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符 號(hào)，所以也稱號(hào)，所以也稱為輸入符號(hào)表；為輸入符號(hào)表；3. . f 是是狀態(tài)狀態(tài)轉(zhuǎn)換函數(shù)，是在轉(zhuǎn)換函數(shù)，是在K*K的子集的映射，即，的子集的映射，即，f: f: K*2K ；表明在某狀態(tài)下對于某；表明在某狀態(tài)下對于某輸入符號(hào)可能有多個(gè)后輸入符號(hào)可能有多個(gè)后繼狀態(tài)；繼狀態(tài)；5. . Z K是一個(gè)終態(tài)集是一個(gè)終態(tài)集（可空）。（可空）。4. S K K是一個(gè)非空初態(tài)集；是一個(gè)非空初態(tài)集； 一一、NFA定義定義：一個(gè)非確定的有窮自動(dòng)機(jī)（一個(gè)非確定的有窮自動(dòng)機(jī)（NFA）M是一個(gè)五元組：是一個(gè)五元組：M=（K，f，S ，Z）,

39、 ,其中其中: :武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌二、一個(gè)二、一個(gè)NFA NFA 的例子：的例子：NFA M=（S，P，Z，0，1，f，S，P，Z）其中其中 ： f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，ZSPZ00,1111狀態(tài)圖表示狀態(tài)圖表示武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌矩陣表示矩陣表示簡化為簡化為0 01 1SPS,Z0 0PZ0 0ZPP1 1+01SPS,Z0PZ0ZPP1+武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌具有具有 轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)轉(zhuǎn)移的不確定的有窮自

40、動(dòng)機(jī)對任何一個(gè)具有對任何一個(gè)具有 轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFAN，一定存在一個(gè)不具有，一定存在一個(gè)不具有 轉(zhuǎn)移的不確定轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)的有窮自動(dòng)機(jī)NFA，使得，使得L(M)=L(N)。定理：定理：與上例等價(jià)的一個(gè)與上例等價(jià)的一個(gè)NFA：c12 3abc2acbb31acabb武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 類似類似DFA, 對對NFA M= K， ，f，S，Z 也有如下定義：也有如下定義：*上的符號(hào)串上的符號(hào)串t t在在NFA M上運(yùn)行：上運(yùn)行：一個(gè)輸入符一個(gè)輸入符號(hào)號(hào)串串 t，（我們將它表示成，（我們將它表示成T t1的形式，其

41、中的形式，其中T，t1 *）在）在NFA M上運(yùn)行的定義為：上運(yùn)行的定義為：f（Q， Tt1）=f（f（Q，T），），t1） 其中其中QK。*上的符上的符號(hào)號(hào)串串 t 被被NFA M接受：接受：若若t *，f(S0，t)=P，其中，其中S0 S，P Z，則稱，則稱 t為為NFA M所所接受（識(shí)別）接受（識(shí)別）武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌* *上的符號(hào)串上的符號(hào)串t t被被NFA MNFA M接受也可以這樣理解接受也可以這樣理解: : 對于對于*中的任何一個(gè)串中的任何一個(gè)串t，若存在一條從，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道某一初態(tài)結(jié)到某一終態(tài)結(jié)的

42、道路，且這條道路上所有弧的標(biāo)記字依序連接成的串路上所有弧的標(biāo)記字依序連接成的串(不理采不理采那些標(biāo)記為那些標(biāo)記為的弧的弧)等于等于t，則稱，則稱t可為可為NFA M所識(shí)別所識(shí)別(讀出或接受讀出或接受)。若。若M的某些結(jié)既是初的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路結(jié)到某個(gè)終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均其上所有弧的標(biāo)記均為為，那么空字可為，那么空字可為M所接受。所接受。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌結(jié)論：結(jié)論： NFA M所能接受的符所能接受的符號(hào)號(hào)串的全體記串的全體記為為 L(M)。 上一個(gè)符

43、上一個(gè)符號(hào)號(hào)串集串集V 是正規(guī)的，是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)當(dāng)且僅當(dāng)存在一個(gè) 上的不確定的有窮上的不確定的有窮自動(dòng)機(jī)自動(dòng)機(jī)M，使得，使得V=L(M)。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌4.3.3 NFA4.3.3 NFA與與DFADFA的等價(jià)性：的等價(jià)性：顯然，顯然， DFA是是NFA的特例。的特例。 對于每個(gè)對于每個(gè)NFA M，存在一個(gè)，存在一個(gè)DFA M ，使，使得得L( M ) =L( M )。對每個(gè)對每個(gè)NFA M存在著與之存在著與之等價(jià)的等價(jià)的DFA M。即：對于任何兩個(gè)有窮自動(dòng)機(jī)即：對于任何兩個(gè)有窮自動(dòng)機(jī)M和和M，如果，如果L( M )=L( M )，則稱

44、，則稱M與與M是等價(jià)的。是等價(jià)的。有一種算法，將有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的轉(zhuǎn)換成接受同樣語言的DFA。這種算法稱為這種算法稱為子集法子集法。與某一與某一NFANFA等價(jià)的等價(jià)的DFADFA不唯一。不唯一。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌 從從NFA的矩陣表示中可以看出，表項(xiàng)通的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在常是一狀態(tài)的集合，而在DFA的矩陣表示中，的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng)的到相應(yīng)的DFA的構(gòu)造的構(gòu)造的基本思路是：的基本思路是： DFADFA的每一個(gè)狀態(tài)對應(yīng)的每一個(gè)狀態(tài)對應(yīng)NFANFA的一組狀態(tài)。的一組

45、狀態(tài)。 DFA使用它的狀態(tài)去記錄在使用它的狀態(tài)去記錄在NFA讀入一讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài)個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài).武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌一、一、NFA確定化算法（確定化算法（NFANFADFADFA的轉(zhuǎn)換）的轉(zhuǎn)換）: 假設(shè)假設(shè)NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造一個(gè)按如下辦法構(gòu)造一個(gè)DFA M=(S, ,d,S0,St)，使得，使得L(M)=L(N)：1. M的狀態(tài)集的狀態(tài)集S由由K K的一些子集的一些子集組成。用組成。用S1 S2. Sj表示表示S的元的元素，其中素，其中S1, S2,. Sj是是K的狀態(tài)。并且約定，狀

46、態(tài)的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是是按某種規(guī)則排列的，即對于子集按某種規(guī)則排列的，即對于子集S1, S2= S2, S1,來說，來說，S的的狀態(tài)就是狀態(tài)就是S1 S2；2 M和和N的輸入字母表是相同的，即是的輸入字母表是相同的，即是 ；3轉(zhuǎn)換函數(shù)是這樣定義的：轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a)4 S0= -closure(K0)為為M的開始狀態(tài)；的開始狀態(tài)；5 St=Si Sk. Se， 其中其中 Si Sk. Se S且且Si , Sk,.

47、Se Kt武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌二、二、定義對狀態(tài)集合定義對狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：的幾個(gè)有關(guān)運(yùn)算：1. 狀態(tài)集合狀態(tài)集合I I的的-閉包閉包，表示為，表示為-closure(I)，定義為一狀，定義為一狀態(tài)集，是狀態(tài)集態(tài)集，是狀態(tài)集I中的任何狀態(tài)中的任何狀態(tài)S經(jīng)任意條經(jīng)任意條弧而能到達(dá)的狀弧而能到達(dá)的狀態(tài)的集合。態(tài)的集合。狀態(tài)集合狀態(tài)集合I的任何狀態(tài)的任何狀態(tài)S都屬于都屬于-closure(I)。2. 狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換，定義狀態(tài)集合定義狀態(tài)集合J表示為表示為 J=move(I,a) ，其中其中J是所有那些可從是所有那些可從I中

48、的某一狀態(tài)經(jīng)過一條中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀弧而到達(dá)的狀態(tài)的全體。態(tài)的全體。Ia=-closure(J ) =-closure(move(I,a) )武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌狀態(tài)集合狀態(tài)集合I的有關(guān)運(yùn)算的例子的有關(guān)運(yùn)算的例子I= 1 , -closure(I) = 1,2 ；I= 5 , -closure(I) = 5,6,2 ；Move ( 1,2 , a ) = 5, 3, 4 -closure( 5, 3, 4 ) = 2, 3,4, 5,6, 7, 8 ；12534687aa a武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌三、

49、三、構(gòu)造構(gòu)造NFA N的的狀態(tài)狀態(tài)K K的子集的子集的算法：的算法： 假定所構(gòu)造的子集族為假定所構(gòu)造的子集族為C，即，即C= (T1, T2,. TI),其中其中T1, T2,. TI為狀態(tài)為狀態(tài)K的子集。的子集。1. 開始，令開始，令 -closure(K0)為為C中唯一成員，并且它是未被標(biāo)中唯一成員，并且它是未被標(biāo)記的。記的。2.while （C中存在尚未被標(biāo)記的子集中存在尚未被標(biāo)記的子集T）do 標(biāo)記標(biāo)記T； for 每個(gè)輸入字母每個(gè)輸入字母a do U:= -closure(move(T,a)； if U不在不在C中中 then 將將 U作為未標(biāo)記的子集作為未標(biāo)記的子集Ti加在加在C中

50、中 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌例子例子aaIaIbi，1，21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fI4f35621i aabbbb武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌等價(jià)的等價(jià)的DFAaCDBAEFSbaaaaabbbbbabF武漢理工

51、大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌4.3.44.3.4確定有窮自動(dòng)機(jī)的化簡確定有窮自動(dòng)機(jī)的化簡 說一個(gè)有窮自動(dòng)機(jī)是化簡了的，即是說，說一個(gè)有窮自動(dòng)機(jī)是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。即等價(jià)的有窮自動(dòng)機(jī)。即用一個(gè)狀態(tài)代替所有與用一個(gè)狀態(tài)代替所有與其等價(jià)的狀態(tài)。其等價(jià)的狀態(tài)。 所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是

52、指這樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。通路到達(dá)終態(tài)。DFA的最小化就是尋求最小狀態(tài)的最小化就是尋求最小狀態(tài)DFA武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌1.沒有多余狀態(tài)沒有多余狀態(tài)(死狀態(tài)死狀態(tài)) )；2.2.沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）。沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）。兩個(gè)狀態(tài)兩個(gè)狀態(tài)s和和t可區(qū)別：可區(qū)別：不滿足不滿足兼容性兼容性同是終態(tài)或同是非終態(tài)；同是終態(tài)或同是非終態(tài)；傳播性傳播性從從s出發(fā)讀入某個(gè)出發(fā)讀入某個(gè)a

53、a和從和從 t 出發(fā)出發(fā)讀入某個(gè)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。到達(dá)的狀態(tài)等價(jià)。一、一、最小狀態(tài)最小狀態(tài)DFA的含義：的含義：兩個(gè)狀態(tài)兩個(gè)狀態(tài)s和和t等價(jià)：等價(jià)： 如果由如果由 s 出發(fā)能導(dǎo)出的所有串的集合與出發(fā)能導(dǎo)出的所有串的集合與 t 出發(fā)能出發(fā)能導(dǎo)出的所有串的集合相等，我們稱狀態(tài)導(dǎo)出的所有串的集合相等，我們稱狀態(tài) s 與狀態(tài)與狀態(tài) t 是是等價(jià)的。等價(jià)的。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌例子例子 C和和D同是終態(tài)，讀入同是終態(tài)，讀入a到達(dá)到達(dá)C和和F，C和和F同同是終態(tài)，是終態(tài)， C和和F讀入讀入a都到達(dá)都到達(dá)C，讀入，讀入b都到達(dá)都到達(dá)E。 C和和D等價(jià)。等價(jià)。a

54、CDBAEFSbaaaaabbbbbabF武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌二、二、“分割法分割法”（逐步分組試探法）（逐步分組試探法）DFA的最小化算法的核心的最小化算法的核心 把一個(gè)把一個(gè)DFA的狀態(tài)分成一些不相交的子集，的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。 算法假定每個(gè)狀態(tài)射出的弧都是完全的算法假定每個(gè)狀態(tài)射出的弧都是完全的,否否則，引入一個(gè)新狀態(tài)，叫死狀態(tài)，該狀態(tài)是非則，引入一個(gè)新狀態(tài)，叫死狀態(tài)，該狀態(tài)是非狀態(tài)，將

55、不完全的輸入弧都射向該狀態(tài)，對所狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己。有輸入，該狀態(tài)射出的弧還回到自己。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌三、三、 DFA的最小化算法的最小化算法設(shè)有設(shè)有DFA M =DFA M =（K,f,kK,f,k0 0 ,k,kz z）, ,最小狀態(tài)最小狀態(tài)DFA MDFA M 1.1. 因?yàn)椴浑y證明，如果因?yàn)椴浑y證明，如果s si i是非終結(jié)狀態(tài)，而是非終結(jié)狀態(tài)，而s sj j是終結(jié)狀態(tài)，那么是終結(jié)狀態(tài)，那么s si i和和s sj j一一定互不等價(jià)（根據(jù)等價(jià)的定義可知，它們導(dǎo)出的符號(hào)串集不同）。所以開定互

56、不等價(jià)（根據(jù)等價(jià)的定義可知，它們導(dǎo)出的符號(hào)串集不同）。所以開始可以把始可以把K K中的終態(tài)和非終態(tài)分開，分成兩個(gè)子集，形成一個(gè)基本劃分：中的終態(tài)和非終態(tài)分開，分成兩個(gè)子集，形成一個(gè)基本劃分： P P2 2II1 1，I I2 2 （I I1 1II2 2K K，I I1 1II2 2）2. 2. 若此兩個(gè)子集還可以進(jìn)行劃分，則作進(jìn)一步的劃分，形成若此兩個(gè)子集還可以進(jìn)行劃分，則作進(jìn)一步的劃分，形成P Pm m , ,假定到某假定到某個(gè)時(shí)候個(gè)時(shí)候P Pm m已經(jīng)含有已經(jīng)含有m m個(gè)子集，記為：個(gè)子集，記為：P Pm mII1 1，I I2 2，I Im m ，設(shè)，設(shè)s s 和和s s 是是I Ii

57、 i中中的任意兩個(gè)狀態(tài)，如果對某個(gè)的任意兩個(gè)狀態(tài)，如果對某個(gè)a,a,存在存在I Ij j ，使，使 f(sf(s ,a), f(s,a), f(s ,a)I,a)Ij j ，則稱則稱s s 和和s s 關(guān)于關(guān)于a a是擬等價(jià)的。是擬等價(jià)的。 如果存在如果存在s s ，s s IIi i，使得對字母表，使得對字母表中的某個(gè)符號(hào)中的某個(gè)符號(hào)a, sa, s 和和s s 不為擬不為擬等價(jià)，則我們說等價(jià)，則我們說I Ii i是可分的。是可分的。 換句話說，令換句話說，令I(lǐng) Ii i ss1 1，s s2 2, , ，s sn n ，如果對某個(gè)，如果對某個(gè)aa，使得，使得I Ia ai i f(s f(

58、s1 1,a),a)，f(sf(s2 2,a),a)，f(sf(sn n,a),a)不全落在現(xiàn)行不全落在現(xiàn)行P Pm m的某一個(gè)子集的某一個(gè)子集I Ij j之中；之中；即即I Ia ai i這個(gè)集合中的元素分別屬于這個(gè)集合中的元素分別屬于I I1 1，I I2 2，I Im m中的幾個(gè)不同集合，則中的幾個(gè)不同集合，則I Ii i可分為幾個(gè)集合（至少可一分為二）?？煞譃閹讉€(gè)集合（至少可一分為二）。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌3 3轉(zhuǎn)轉(zhuǎn)2,2,上述過程務(wù)必一再重復(fù)，直到上述過程務(wù)必一再重復(fù)，直到P P中的每個(gè)集合均是不可再分時(shí)為止。中的每個(gè)集合均是不可再分時(shí)為止。

59、此時(shí)，此時(shí)，P P所含的集合數(shù)不再增加，即所含的集合數(shù)不再增加，即P P中的每個(gè)集合中的狀態(tài)互相等價(jià)，而中的每個(gè)集合中的狀態(tài)互相等價(jià)，而不同集合間的狀態(tài)互不等價(jià)。不同集合間的狀態(tài)互不等價(jià)。4.4.為為P P中的每一組選一代表，這些代表構(gòu)成中的每一組選一代表，這些代表構(gòu)成M M 的狀態(tài)。把原來導(dǎo)入非代表狀的狀態(tài)。把原來導(dǎo)入非代表狀態(tài)的弧均導(dǎo)入其代表即可，即若態(tài)的弧均導(dǎo)入其代表即可，即若k k 是一代表且是一代表且f(kf(k ,a)=t,a)=t,令令r r是是t t組的代表，組的代表，則則M M 中有一轉(zhuǎn)換中有一轉(zhuǎn)換f f (k(k ,a)=r,a)=r，M M 的開始狀態(tài)是含有的開始狀態(tài)是含

60、有S S0 0的那組的代表，的那組的代表，M M 的終的終態(tài)是含有態(tài)是含有F F的那組的代表。的那組的代表。5.5.去掉去掉M M 中的死狀態(tài)。中的死狀態(tài)。 例：有例：有DFA M見右圖，求見右圖，求其極小化后的其極小化后的DFA M 。b23641babaaaababb5ab7武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌4.4 4.4 正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性一、定理：一、定理：1.對于對于 上的上的NFA M，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè) 上的正規(guī)式上的正規(guī)式R，使得，使得L（R）=L（M）。）。2.對于對于 上的任一個(gè)正規(guī)式上的任一個(gè)正規(guī)式R ，