《詞法分析》ppt課件

1、第四章 詞法分析考查重點(diǎn)考查重點(diǎn)1. 基本概念基本概念 ：正規(guī)式正規(guī)式、正規(guī)集、有窮自、正規(guī)集、有窮自動(dòng)機(jī)動(dòng)機(jī)(DFA與與NFA）2. 基本方法：基本方法： 由正規(guī)文法或自然語(yǔ)言描述求正規(guī)式由正規(guī)文法或自然語(yǔ)言描述求正規(guī)式 由正規(guī)式構(gòu)造有窮自動(dòng)機(jī)由正規(guī)式構(gòu)造有窮自動(dòng)機(jī)(FA) 確定化確定化(NFADFA)，DFA最小化最小化 正規(guī)文法與有窮自動(dòng)機(jī)轉(zhuǎn)換正規(guī)文法與有窮自動(dòng)機(jī)轉(zhuǎn)換4.1 詞法分析程序的設(shè)計(jì)詞法分析程序的設(shè)計(jì)1、詞法分析、詞法分析（lexical analysis）逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行。也可以和語(yǔ)法分析結(jié)合在

2、一起作為一遍，由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。單詞是語(yǔ)言中具有獨(dú)立意義的最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。2、詞法分析程序、詞法分析程序源程序源程序詞法分析程序詞法分析程序語(yǔ)法分析程序語(yǔ)法分析程序Tokenget token.主要任務(wù)主要任務(wù)：讀源程序，產(chǎn)生讀源程序，產(chǎn)生單詞符號(hào)單詞符號(hào)其他任務(wù)其他任務(wù)：濾掉空格，跳過(guò)注釋、換行符濾掉空格，跳過(guò)注釋、換行符追蹤換行標(biāo)志，標(biāo)志出錯(cuò)源程序，追蹤換行標(biāo)志，標(biāo)志出錯(cuò)源程序，宏展開，宏展開，單詞符號(hào)一般可分為下列五種： 1、基本字（關(guān)鍵字）：if, while, 等 2、標(biāo)識(shí)符標(biāo)識(shí)符：如常量名、變量名、過(guò)

3、程名等 3、常數(shù)（量）：25, 3.1415, TRUE, “ABC”等 4、運(yùn)算符：如 + - * / =等 5、界符：逗號(hào)，分號(hào)，括號(hào)等輸出表示（單詞類別，單詞自身的值） 例： A:=B+2 (2,指向指向A的符號(hào)表的入口指針的符號(hào)表的入口指針）(4, :=) (2,指向指向B的符號(hào)表的入口指針的符號(hào)表的入口指針) (4,+) (3, 2)詞法分析工作獨(dú)立的原因： 簡(jiǎn)化設(shè)計(jì)：詞法分析比語(yǔ)法分析簡(jiǎn)單，如果與語(yǔ)法分析一起，會(huì)導(dǎo)致程序結(jié)構(gòu)復(fù)雜。 改進(jìn)編譯效率：編譯的大部分時(shí)間花在掃描字符區(qū)分單詞上，專門的詞法分析可加快編譯速度。 增加編譯系統(tǒng)的可移植性。 4.2 單詞的描述工具 詞法詞法： 單詞

4、符號(hào)的文法，用來(lái)描述高級(jí)語(yǔ)言中的：標(biāo)識(shí)符、常數(shù)、運(yùn)算符、分界符、關(guān)鍵字單詞的描述工具：?jiǎn)卧~的描述工具： 正規(guī)文法 正規(guī)式 一、正規(guī)文法與單詞描述一、正規(guī)文法與單詞描述1、正規(guī)、正規(guī)文法文法G=（VN，VT，P，S），P中每一產(chǎn)生式的形式都為： 右線性： AaB Aa 左線性： ABa Aa 其中AVN ，BVN ，aVT注注：正規(guī)文法中可能既右線性文法又左線性文法：正規(guī)文法中可能既右線性文法又左線性文法?。2、程序設(shè)計(jì)語(yǔ)言幾類單詞的描述、程序設(shè)計(jì)語(yǔ)言幾類單詞的描述 如：程序設(shè)計(jì)語(yǔ)言( l 表示az中的任一英文字母,d表示09中的任一數(shù)字。) l|l l|d|l|d d| d +|-|*| /

5、| = | | = if | while | else無(wú)符號(hào)實(shí)數(shù)無(wú)符號(hào)實(shí)數(shù)：（其中s表示正或負(fù)號(hào)) 無(wú)符號(hào)實(shí)數(shù) d 余留無(wú)符號(hào)數(shù)| . 十進(jìn)小數(shù) | e指數(shù)部分 余留無(wú)符號(hào)數(shù) d 余留無(wú)符號(hào)數(shù)| . 十進(jìn)小數(shù) | e指數(shù)部分| 十進(jìn)小數(shù) d 余留十進(jìn)小數(shù)余留十進(jìn)小數(shù) e指數(shù)部分| d 余留十進(jìn)小數(shù)| 指數(shù)部分 d 余留整指數(shù)| s整指數(shù)整指數(shù) d 余留整指數(shù)余留整指數(shù) d 余留整指數(shù) | 如 25.55e+5 和 2.1 思考思考：以上文法為幾型文法？：以上文法為幾型文法？ 二、正規(guī)式二、正規(guī)式和正規(guī)集正規(guī)集 1、正規(guī)式正規(guī)式和正規(guī)集遞歸定義：正規(guī)集遞歸定義： 字母表字母表 ，輔助表，輔助表

6、= ， ， ， ， ， ， 和都是上的正規(guī)式，它們所表示的 正規(guī)集分別為和； 任何a ，a是上的一個(gè)正規(guī)式，它所 表示的正規(guī)集為a； 假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，那么，(e1), e1e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集正規(guī)集。相關(guān)說(shuō)明相關(guān)說(shuō)明： 其中“”讀“或”（也可用“+”代替 “” 的）“ ”讀“連接”；“”讀“閉包”（任意有限次的自重復(fù)連

7、接） 連接符“ ”一般可省略不寫。 “(”,“)”并非正規(guī)式的運(yùn)算符。 規(guī)定算符的優(yōu)先順序?yàn)椤啊?、?”、“” 。 “”、“ ”和“” 都是左結(jié)合的。 在不致混淆時(shí)，括號(hào)可省去。 如：(r (s*)|r)=rs*|r r *(s*|r)圓括號(hào)不可略去例例4.2 令=a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集（特點(diǎn)特點(diǎn)）a aaba,bab aba ,a,a, 任意個(gè)a的串(ab) ,a,b,aa,ab 所有由a 和b組成的串(ab)(ab) aa,ab,ba,bb(ab)(aabb)(ab)上所有含有兩個(gè)相繼 的a或兩個(gè)相繼的b組成 的串思考思考：表示上所有以a開始，以b結(jié)尾串

8、的正規(guī)式？ 程序設(shè)計(jì)語(yǔ)言中的單詞都可由正規(guī)式來(lái)定義：程序設(shè)計(jì)語(yǔ)言中的單詞都可由正規(guī)式來(lái)定義：例 =l，d，r=l(l d) 定義的正規(guī)集: l,ll,ld,ldd,（標(biāo)識(shí)符標(biāo)識(shí)符）例4.3 =d，.，e，+，-,則上的正規(guī)式 dd (.dd )(e(+ - )dd )表示的是無(wú)符號(hào)無(wú)符號(hào)數(shù)數(shù)的集合的集合。其中d為09的數(shù)字。如：2，12.59, 3.6e2, 4.71e-1（參考P49）2、若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同,則說(shuō)e1和和e2等價(jià)等價(jià),寫作e1=e2。 例如： e1= (a|b)， e2 = b|a 又如： e1= b(a|b)* , e2 =b (b|a)*3、正規(guī)式的

9、運(yùn)算律、正規(guī)式的運(yùn)算律 設(shè)r,s,t為正規(guī)式， 1、rs=sr“或”服從交換律2、r(st)=(rs)t“或”的可結(jié)合律3、(rs)t=r(st)“連接”的可結(jié)合律4、r(st)=rsrt (st)r=srtr 分配律 5、 r=r, r=r是“連接”的恒等元素6、 rr=r r=rrr“或”的抽取律 4、正規(guī)文法、正規(guī)文法 正規(guī)語(yǔ)言正規(guī)語(yǔ)言 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 ： 由正規(guī)文法產(chǎn)生的語(yǔ)言稱正規(guī)集（正規(guī)語(yǔ)言）正規(guī)集正規(guī)集是一個(gè)有窮或者無(wú)窮的集合，可用正規(guī)式(Regular Expression,Re)來(lái)描述。正規(guī)式正規(guī)式也稱正則表達(dá)式,正規(guī)表達(dá)式是說(shuō)明單詞的模式(pattern)的一種重

10、要的表示法(記號(hào))，是定義正規(guī)集的數(shù)學(xué)工具。正規(guī)式描述的集合稱作正規(guī)集。正規(guī)文法與正規(guī)式具有等價(jià)性等價(jià)性。單詞更適合用正規(guī)式（直觀直觀）來(lái)定義。對(duì)對(duì) 上的正規(guī)式上的正規(guī)式r ,存在一個(gè)存在一個(gè)G=(VN,VT,P,S)使得使得L(G)=L(r) ，反之亦然反之亦然。三、正規(guī)文法與正規(guī)式的等價(jià)性三、正規(guī)文法與正規(guī)式的等價(jià)性 1、正規(guī)文法轉(zhuǎn)換成正規(guī)式、正規(guī)文法轉(zhuǎn)換成正規(guī)式方法：由正規(guī)文法方法：由正規(guī)文法G的各個(gè)產(chǎn)生式寫出對(duì)應(yīng)的正規(guī)方的各個(gè)產(chǎn)生式寫出對(duì)應(yīng)的正規(guī)方程式，聯(lián)立方程組。程式，聯(lián)立方程組。 引進(jìn)引進(jìn)S作為識(shí)別符號(hào)作為識(shí)別符號(hào),利用以下利用以下規(guī)則做變換規(guī)則做變換 文法產(chǎn)生式文法產(chǎn)生式 正規(guī)式

11、正規(guī)式 規(guī)則規(guī)則1 AxB By A=xy 規(guī)則規(guī)則2 AxA|y A=x*y AAx|y A=yx* 規(guī)則規(guī)則3 Ax Ay A=x|y 變?cè)欠墙K結(jié)符變?cè)欠墙K結(jié)符，求解正規(guī)方程式組，最后開始符，求解正規(guī)方程式組，最后開始符號(hào)號(hào)S的解：的解：S= , V T*，即為正規(guī)式即為正規(guī)式。例例：文法GS SaA Sa AaA AdA Aa Ad 轉(zhuǎn)換過(guò)程如下： S=aA|a = a(A|) A=(aA|dA)|(a|d) = (a|d)A|(a|d) A= (a|d)*(a|d) S= a(a|d)*(a|d)|) S= a(a|d)* / S= a(a|d)+| ) ？求求：文法GS SSc|

12、Bc BBb|Ab AAa|a 得正規(guī)式。 S= Sc | Bc = Sc | aa* bb*c = aa* bb*cc*思考思考: 什么條件下需要正規(guī)文法轉(zhuǎn)換成正規(guī)式什么條件下需要正規(guī)文法轉(zhuǎn)換成正規(guī)式? 2、將正規(guī)式轉(zhuǎn)換成正規(guī)文法、將正規(guī)式轉(zhuǎn)換成正規(guī)文法引進(jìn)引進(jìn)S作為識(shí)別符號(hào)作為識(shí)別符號(hào), VT= ， VN與與P利用以下利用以下規(guī)則做變換產(chǎn)生：規(guī)則做變換產(chǎn)生： 正規(guī)式正規(guī)式r Sr 正規(guī)式正規(guī)式xy AxB By B新引進(jìn)新引進(jìn)VN？ 正規(guī)式正規(guī)式x*y AxA|y 正規(guī)式正規(guī)式x|y Ax Ay直到每個(gè)產(chǎn)生式直到每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符為止最多含有一個(gè)終結(jié)符為止。注意注意：正規(guī)式的字母

13、表與正規(guī)文法的字母表：正規(guī)式的字母表與正規(guī)文法的字母表？例例：將 r = a(ad)轉(zhuǎn)換成相應(yīng)的正規(guī)文法。Sa(ad)SaAA(a d) A(a d)A AGS: SaA Aa A Ad A A 思考思考：正規(guī)式對(duì)應(yīng)的正規(guī)文法唯一？語(yǔ)言？ GS：S S(ad) a思考思考: 什么條件下需要正規(guī)式轉(zhuǎn)換成正規(guī)文法什么條件下需要正規(guī)式轉(zhuǎn)換成正規(guī)文法?4.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)1.確定的有窮自動(dòng)機(jī) (Deterministic Finite Automata) 2.不確定的有窮自動(dòng)機(jī)(Nondeterministic Finite Automata)3.NFA DFA 的轉(zhuǎn)換4.DFA的化簡(jiǎn)自動(dòng)機(jī)相

14、關(guān)概念自動(dòng)機(jī)相關(guān)概念1、如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。途經(jīng)： 生成方式生成方式 （文法文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。 識(shí)別方式識(shí)別方式（自動(dòng)機(jī)自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是是”，若不屬于，要么能停止并回答“不是不是”，（要么永遠(yuǎn)繼續(xù)下去。） 2、為了構(gòu)造詞法分析程序，要研究構(gòu)詞法，每種詞類的結(jié)構(gòu)模式以及識(shí)別它的數(shù)學(xué)模型數(shù)學(xué)模型有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)。 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即正規(guī)文法所定義的語(yǔ)言或正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找

15、特殊的方法和工具。 有窮自動(dòng)機(jī)分為兩類： DFA和NFA 。 1、DFA定義定義：一個(gè)確定的有窮自動(dòng)機(jī)（一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：是一個(gè)五元組：M=（K，f，S，Z）其中：其中：K K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)狀態(tài)；是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱所以也稱為為輸入符號(hào)字母表輸入符號(hào)字母表；f f是是轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)，是在，是在KK上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味著，當(dāng)前狀態(tài)就意味著，當(dāng)前狀態(tài)為為ki，輸入符

16、為輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把我們把kj稱作稱作kiki的一個(gè)后繼狀態(tài)；（的一個(gè)后繼狀態(tài)；（單值函數(shù)單值函數(shù)）S SK K是是唯一唯一的一個(gè)的一個(gè)初態(tài)初態(tài)；Z Z K是一個(gè)是一個(gè)終態(tài)終態(tài)集集，終態(tài)也稱，終態(tài)也稱可接受狀態(tài)可接受狀態(tài)或或結(jié)束狀態(tài)結(jié)束狀態(tài)。一、確定的有窮自動(dòng)機(jī)一、確定的有窮自動(dòng)機(jī)DFA 例： M=（S,U,V,Q, a,b, f, S, Q） f 為：為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V , b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q 2、 的表示的表示： 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖：設(shè)有m個(gè)狀態(tài)和

17、n個(gè)輸入字符，圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多只能有n條弧從結(jié)點(diǎn)射出并與別的結(jié)點(diǎn)相連結(jié)，每條弧上的標(biāo)記是字母表上的一個(gè)字符。圖只有一個(gè)初態(tài)結(jié)點(diǎn)，用雙箭頭雙箭頭射入的節(jié)點(diǎn)表示初態(tài)，終態(tài)可由若干個(gè)，用雙圓圈雙圓圈表示。 狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)轉(zhuǎn)換矩陣：行表示狀態(tài)，列表示輸入字符，矩陣元素表示f(s,a)的值。2-1、DFA 的狀態(tài)圖表示的狀態(tài)圖表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（ V , b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bb2-2、DFA 的矩陣表示的矩陣表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V ，b

18、）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q字符狀態(tài)01003、 DFA 接受的字符串接受的字符串 為了說(shuō)明DFA如何作為一種識(shí)別機(jī)制,我們還要理解下面的定義 3-13-1、* *上的符號(hào)串上的符號(hào)串t t在在M M上運(yùn)行上運(yùn)行 一個(gè)輸入符號(hào)串t，（我們將它表示成at1的形式，其中a，t1 *）在DFA M上運(yùn)行的定義為：f（A， at1）=f（f（A，a），t1） 其中AK 擴(kuò)充轉(zhuǎn)換函數(shù)f，是K*K上的映射，且： f（A，）= A3-2、*上的符上的符號(hào)號(hào)串串 t 被被 M 接受接受對(duì)于*中的任何字符串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的的標(biāo)

19、記符連接成的字符串等于t，則稱t可為DFA M所接受，若M的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則空字可為M所接受（識(shí)別接受（識(shí)別）。若t *，f(S，t)=P，其中S為DFA M的開始狀態(tài)，P Z，Z為終態(tài)集。則稱t為DFA M所接受（識(shí)別）接受（識(shí)別）。4、例例：證明：證明t=baab被如下的被如下的DFA所接受所接受DFA M=（S,U,V,Q, a,b, f, S, Q）f 定義為：定義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（ V , b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb證明證明： f（S，baab）=f（f（S，b），a

20、ab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，a），b）=f（Q，b）=Q Q屬于終態(tài)。得證。屬于終態(tài)。得證。5、從狀態(tài)轉(zhuǎn)換圖看、從狀態(tài)轉(zhuǎn)換圖看：5-1、能被接受的字符串： 存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧的標(biāo)記符連成的字符串為t，則t被DFA接受。 若初態(tài)同時(shí)也是終態(tài)，則空串可被接受。 5-2、不能被接受的字符串：讀完輸入串，狀態(tài)不停在終態(tài)；在讀過(guò)程中出現(xiàn)不存在映射，使自動(dòng)機(jī)無(wú)法繼續(xù)動(dòng)作。 6、DFA M 接受的語(yǔ)言接受的語(yǔ)言 DFA M接受的全體字符串為接受的全體字符串為M 接受的語(yǔ)言接受的語(yǔ)言,記為記為()。結(jié)論結(jié)論：上的一個(gè)字符串集上的

21、一個(gè)字符串集V *是是正規(guī)正規(guī)的，當(dāng)且僅當(dāng)存在的，當(dāng)且僅當(dāng)存在一個(gè)一個(gè)上的確定有窮自動(dòng)機(jī)上的確定有窮自動(dòng)機(jī)M使得使得V=L(M)。二、不確定的有窮自動(dòng)機(jī)二、不確定的有窮自動(dòng)機(jī)NFA1、定義、定義：M=K，f，S，Z，其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集的映像（多值函數(shù)多值函數(shù)），SK是初始狀態(tài)集(初始態(tài)可多個(gè)初始態(tài)可多個(gè)) ，Z K為終止?fàn)顟B(tài)集。例例 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,11112-1、狀態(tài)圖表示、狀態(tài)圖表示思考思考：DFA與NFA

22、的主要區(qū)別？ 2-2表格表示表格表示(較少采用較少采用 ？)01SPS,Z0PZ0ZPP1簡(jiǎn)化簡(jiǎn)化01SPS,Z0P.Z0ZPP1NFA M=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P3、 相關(guān)說(shuō)明相關(guān)說(shuō)明： *上的符號(hào)串t在NFA M上運(yùn)行 *上符號(hào)串t被NFA M接受（識(shí)別） DFA是是NFA的特例的特例。SPZ00,11114、有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)M=(K,f, S,Z）行為模擬程序行為模擬程序：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是是”，若不屬于，要么能停止

23、并回答“不是不是” K:=S；c:=getchar;while ceof do K:=f(K,c); /？ c:=getchar; ;if K is in Z then return (yes) else return (no)bSUVQaaaba，bb以文件存串以文件存串baab為為例例三、三、NFA的確定化的確定化1、定理、定理 ： 對(duì)任何一個(gè)NFA N，都存在一個(gè) DFA M，使L(M)=L(N).證明思想證明思想：子集構(gòu)造法 從NFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)集合狀態(tài)集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)一個(gè)狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本思路是： DFA的每一

24、個(gè)狀態(tài)對(duì)應(yīng)的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一的一組狀態(tài)組狀態(tài)。DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài). 注注： 與某一NFA等價(jià)的DFA不唯一不唯一。2、 定義對(duì)狀態(tài)集合定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算的幾個(gè)有關(guān)運(yùn)算狀態(tài)集合I的-閉包： -closure(I) 定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達(dá)的狀態(tài)的集合。約定約定狀態(tài)集合I的任何狀態(tài)都屬于 -closure(I) 狀態(tài)集合I的a弧轉(zhuǎn)換：move(I,a) 定義為狀態(tài)集合J，其中J是所有那些可從I的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。例例： I=1, -closure(I)=1,2； move(

25、1,a)=5, 4； move(1,2,a)=？；- closure(5,3,4)=？； - closure（move(1,2,a)）12534687aaa3、 NFADFA NFA N=(K, ,f,K0,Kt) DFA M=(S, ,D,S0,St ） M的狀態(tài)集S由K的一些子集組成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的狀態(tài)。約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對(duì)于子集S1, S2= S2, S1,來(lái)說(shuō)，S的狀態(tài)是S1 S2； M和N的輸入字母表是相同的，即是； 轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)是這樣定義的： D(S1 ,S2 ,. , Sj,a)= R1

26、, R2 ,. , Rt 其中 ：R1 , R2 ,. , Rt = -closure(move(S1 ,S2 ,. , Sj,a) S0=-closure(K0)為M的開始狀態(tài)； St=Si ,Sk ,.,Se，其中Si ,Sk ,. ,SeS且Si , Sk,. SeKt4、構(gòu)造、構(gòu)造NFA N的狀態(tài)的狀態(tài)K的的子集子集的算法的算法：假定所構(gòu)造的子集族為C，即C= (T0, T1,. TI),其中T0, T1,. TI為狀態(tài)K的子集。 開始，令 -closure(K0)為C中唯一成員，并且它是未被標(biāo)記未被標(biāo)記的。 while （C中存在尚未被標(biāo)記的子集中存在尚未被標(biāo)記的子集Ti） do 標(biāo)

27、記標(biāo)記T； for 每個(gè)輸入字母a do Ti:= -closure(move(T,a)； if Ti不在C中 then 將Ti作為未標(biāo)記的子集加在作為未標(biāo)記的子集加在C中中 5、例例 將下圖的將下圖的-NFA NFA N轉(zhuǎn)換成轉(zhuǎn)換成DFA M023456789101bbbaaNFA N思考思考：如何鑒別上圖為：如何鑒別上圖為NFA 而非而非DFA？023456789101bbbaa狀態(tài)狀態(tài)-closure(move(Ti,a)-closure(move(Ti,b)T0= 0,1,2,4,71,2,3,4,6,7,8加入為T11,2,4,5,6,7 加入為T2T1= 1,2,3,4,6,7,8

28、 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入為T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,7,10 加入為T4T4= 1,2,4,5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2 -closure(0)=0,1,2,4,7初態(tài)終態(tài)b02134abaaaabbbDFA M思考思考：若若NFA N無(wú)無(wú) ，運(yùn)算有何不同？運(yùn)算有何不同？狀態(tài)狀態(tài)S-closure(move(Ti,a)-c

29、losure(move(Ti,b)T0= =0,1,2,4,71,2,3,4,6,7,8加入為T11,2,4,5,6,7 加入為T2T1= 1,2,3,4,6,7,8 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入為T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,7,10 加入為T4T4= 1,2,4,5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2四、四、DFA的最小化（化簡(jiǎn)）的最小化

30、（化簡(jiǎn)）1、有窮自動(dòng)機(jī)最小狀態(tài)、有窮自動(dòng)機(jī)最小狀態(tài)DFA要求：要求： 沒有多余狀態(tài)(死狀態(tài)) 多余狀態(tài)多余狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別） 兩個(gè)狀態(tài)兩個(gè)狀態(tài)s和和t等價(jià)等價(jià)：滿足 一致性s與t 同是終態(tài)或同是非終態(tài) 蔓延性對(duì)于任意任意a,f(s,a)=p,f(t,a)=q, p和和q必須等價(jià)必須等價(jià) 2、消除多余狀態(tài)、消除多余狀態(tài)s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s

31、2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7思考思考：狀態(tài)圖中如何鑒別多余狀態(tài)？狀態(tài)圖中如何鑒別多余狀態(tài)？ 狀態(tài)0和4是可區(qū)別可區(qū)別的。 狀態(tài)2和3是可區(qū)別的，why思考思考： 有多余狀態(tài)的嗎？ 此圖中四種狀態(tài)都是可區(qū)別的嗎？判定兩個(gè)狀態(tài)判定兩個(gè)狀態(tài)s和和t不等價(jià)不等價(jià)：只要找到一個(gè) w*, 使f（s,w)F 且f（t,w)!F，或者相反。b02134abaaaabbbDFA M3、狀態(tài)不等價(jià)、狀態(tài)不等價(jià)4、D

32、FA最小化最小化 對(duì)于一個(gè)對(duì)于一個(gè)DFA M =DFA M =（K,f, kK,f, k0 0,k,kt t) )，存在一個(gè)存在一個(gè)最小狀態(tài)最小狀態(tài)DFA M = =（K,f, K,f, k k0 0, ,k,kt t)，,使使L(M)=L(M). 算法的核心算法的核心： 把一個(gè)把一個(gè)DFA的狀態(tài)分成一些不相交的子集，的狀態(tài)分成一些不相交的子集，使使得任何不同的兩子集的狀態(tài)都是可區(qū)別的得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而，而同一子集中同一子集中 的任何兩個(gè)狀態(tài)都是等價(jià)的的任何兩個(gè)狀態(tài)都是等價(jià)的. 結(jié)論：結(jié)論： 接受接受L的最小狀態(tài)有窮自動(dòng)機(jī)的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)不計(jì)同構(gòu)是是唯一唯一的

33、。的。5、將下圖中的、將下圖中的DFA M最小化最小化 1,2,3,4,5,6,7Ia: 6,7,1,4,7,4,4Ib: 3,3,5,6,3,1,21,2,3,4 5,6,71,2 3,4 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbb13546aaaaabbbbb4.4 正規(guī)式正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性和有窮自動(dòng)機(jī)的等價(jià)性1. 對(duì)于上的NFA M，可以構(gòu)造一個(gè)上的正規(guī)式R,使得L(R)=L(M)。2. 對(duì)于上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)上的NFA M，使得L(M)=L(R)。1、自動(dòng)機(jī)自動(dòng)機(jī) NFA M NFA M 正規(guī)式正規(guī)式R R在在M的狀態(tài)轉(zhuǎn)換圖上的狀

34、態(tài)轉(zhuǎn)換圖上加進(jìn)兩個(gè)結(jié)點(diǎn)加進(jìn)兩個(gè)結(jié)點(diǎn)，x與與y結(jié)點(diǎn)。從結(jié)點(diǎn)。從x結(jié)點(diǎn)用結(jié)點(diǎn)用弧連接到弧連接到M的的所有初態(tài)結(jié)點(diǎn)所有初態(tài)結(jié)點(diǎn)，從，從所有終態(tài)結(jié)所有終態(tài)結(jié)點(diǎn)點(diǎn)用用弧連接到弧連接到y(tǒng)結(jié)點(diǎn)。形成一個(gè)與結(jié)點(diǎn)。形成一個(gè)與M等價(jià)的等價(jià)的M,M只只有有一個(gè)初態(tài)一個(gè)初態(tài)x和和一個(gè)終態(tài)一個(gè)終態(tài)y。利用利用消去規(guī)則消去規(guī)則消去消去M中所有結(jié)點(diǎn)，直至剩下中所有結(jié)點(diǎn)，直至剩下x和和y。x和和y結(jié)點(diǎn)間弧上的標(biāo)記則為所求正規(guī)式結(jié)點(diǎn)間弧上的標(biāo)記則為所求正規(guī)式R。123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R3例例：03124a,baaa,ba,bbb求該求該NFA所對(duì)應(yīng)的正規(guī)式所

35、對(duì)應(yīng)的正規(guī)式R.03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy 加進(jìn)加進(jìn)x與與y結(jié)點(diǎn)結(jié)點(diǎn) 利用利用消去規(guī)則消去規(guī)則消去所有結(jié)點(diǎn)消去所有結(jié)點(diǎn)024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy0a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)* |bb(a|b)*xy(a|b)* (aa |bb)(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)* x和和y結(jié)點(diǎn)間弧上的標(biāo)記為結(jié)點(diǎn)間弧上的標(biāo)記為正規(guī)式正規(guī)式R（熟練可直接寫熟練可直接寫）2、正規(guī)式正規(guī)式R R自動(dòng)機(jī)自動(dòng)機(jī)NFA M 首先將首先將正規(guī)式分解為一系列子表達(dá)式，然后正規(guī)式分解為一系列子表達(dá)式，然后使用以下規(guī)則為使用以下規(guī)則為R R構(gòu)造自動(dòng)機(jī)。構(gòu)造自動(dòng)機(jī)。 簡(jiǎn)單（未含運(yùn)算符）正規(guī)式對(duì)應(yīng)簡(jiǎn)單（未含運(yùn)算符）正規(guī)式對(duì)應(yīng)NFA ： R= R= R=a, , 設(shè)設(shè) s,t 為為正規(guī)式，對(duì)應(yīng)的正規(guī)式，對(duì)應(yīng)的NFA為N(s)與N(t)。 R =s | t R =s t, R =s* 例例:為為R=(a|b)*abb構(gòu)造構(gòu)造NFA N，23a54bR=(a|b)*abbR=(a|b)*