【正文】 (S,101)= ? (? (S,1),01)= ? (A,01)= ? (? (A,0),1)= ? (C,1)= B(拒絕 ) 所有為自動(dòng)機(jī) M所能接受的串組成一個(gè)集合，稱這個(gè)集合為自動(dòng)機(jī) M所能接受的語(yǔ)言，用 L(M)表示： L(M)={ t | f(S,t) ?Z， t?Σ *} 對(duì)于任何兩個(gè)有窮自動(dòng)機(jī) M和 M’，如果 L(M)=L(M’ )，則稱 M與 M’是等價(jià)的。 擴(kuò)充的轉(zhuǎn)換函數(shù) f （ 1）設(shè) Q?K，函數(shù) f(Q,ε )=Q，即如果輸入字符是空串，則仍停留在原來(lái)的狀態(tài)上。 二、 狀態(tài)轉(zhuǎn)換表 DFA的映射關(guān)系可以由一個(gè) 矩陣表示，矩陣的行標(biāo)表示狀態(tài)，列標(biāo)表示輸入字符，矩陣元素表示 f(s,a)的值，這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換表。 f(ki， a)＝ kj（ ki,kj Ｑ ,a Σ）kj稱為 ki的一個(gè)后繼狀態(tài)。 (ｂ ) Σ是一個(gè)字母表，它的每個(gè)元素稱為一個(gè)輸入字符。它的模擬程序可以作為詞法分析程序的控制程序。 課前思考 ◇ 什么是有窮自動(dòng)機(jī)？ ◇ 什么是狀態(tài)轉(zhuǎn)換圖？ 章節(jié)內(nèi)容 第一節(jié) 有窮自動(dòng)機(jī)的形式定義 第二節(jié) NFA 到 DFA 的轉(zhuǎn)換 第三節(jié) 正規(guī)文法與有窮自動(dòng)機(jī) 第四節(jié) 正規(guī)表達(dá)式與 FA 第五節(jié) DFA 在計(jì)算機(jī)中的表示 第三章 有窮自動(dòng)機(jī) 2 有窮自動(dòng)機(jī)的形式定義 有窮狀態(tài)自動(dòng)機(jī) (Finitestate Automata 或簡(jiǎn)稱 FA)在識(shí)別功能上與正規(guī)文法類等價(jià)，而且也等價(jià)于一個(gè)特殊類型的語(yǔ)言產(chǎn)生器 —— 正規(guī)表達(dá)式 (Regular Expression)。要求掌握正則文法、狀態(tài)轉(zhuǎn)換圖、 DFA、 NFA、正規(guī)式和正規(guī)集的基本概念 。 教學(xué)內(nèi)容： 本章介紹有關(guān)有窮自動(dòng)機(jī)的基本概念和理論以及正規(guī)文法、正規(guī)表達(dá)式與有窮自動(dòng)機(jī)之間的相互關(guān)系 。因此許多簡(jiǎn)單的程序語(yǔ)言都可由 FA 所識(shí)別。 有窮自動(dòng)機(jī) (也稱有限自動(dòng)機(jī) )作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語(yǔ)言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。 (ｃ ) S K， S 稱為初始狀態(tài) ， 唯一。 確定性的體現(xiàn)：初始狀態(tài)唯一； 轉(zhuǎn)換函數(shù)為單值映射。 例： 第三章 有窮自動(dòng)機(jī) 3 q1 a a a b b a b b q2 q3 q0 a b S U V U Q V V U Q Q Q Q f(S， a)＝ U f(S， b)＝ V f(U， a)＝ Q f(U， b)＝ V f(V， a)＝ U f(V， b)＝ Q f(Q， a)＝ Q f(Q， b)＝ Q 三、狀態(tài)轉(zhuǎn)換圖 圖中標(biāo)有 ?的為開(kāi)始狀態(tài)，標(biāo)有雙圈的狀態(tài)為終止?fàn)顟B(tài)。 （ 2）對(duì) ?Q?K， T?Σ， t1?Σ *， f(Q,Tt1)=f(f(Q,T), t1) 該定義是一個(gè)遞歸定義，說(shuō)明當(dāng)自動(dòng)機(jī)處在狀態(tài) Q且面臨某個(gè)輸入串 Tt1時(shí)，則首先應(yīng)用函數(shù) f(Q,T)=P，然后應(yīng)用函數(shù)f(P,t1)。 五 、非確定有窮自動(dòng)機(jī) NFA定義 一個(gè)不確定的有窮自動(dòng)機(jī) NFA M’是一個(gè)五元組： M’ =(K, Σ ,f,S,Z) 一個(gè)含有 m個(gè)狀態(tài)和 n個(gè)輸入字符的 NFA可表示為一張狀態(tài)轉(zhuǎn)換圖，該圖含有 m個(gè)狀態(tài)結(jié)，每個(gè)結(jié)可射出若干條箭弧與別的結(jié)點(diǎn)相連接，每條弧用Σ *中的一個(gè)字（不一定要不同的字，且可以為空字）作標(biāo)記（稱輸入字），整個(gè)圖至少含有一個(gè)初態(tài)結(jié)以及若干個(gè)終態(tài)結(jié)。 對(duì)于Σ *中的任何一個(gè)串 t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道第三章 有窮自動(dòng)機(jī) 5 輸入字符 狀態(tài) a b 0 {0,3} {0,1} 1 ? {2} 2 {2} {2} 3 {4} ? 4 {4} {4} 0 3 4 1 2 a a b b a,b a,b a,b 路上的所有弧的標(biāo)記依序連接成的串等于 t，則稱 t可為 NFA M所識(shí)別（讀出或接受）。 定義：假定 I是 NFA M中狀態(tài)集的一個(gè)子集， a?Σ ，定義 Ia=ε _closure(J) 其中 J是所有那些可從子集 I中的任一狀態(tài)出發(fā)，經(jīng)過(guò)一條 a連線 (跳過(guò) a連線前的ε連線 )而到達(dá)的狀態(tài) (結(jié) )的全體。然后計(jì)算它的 Ia 和 Ib,分別填入第二、三列上，一般，若某一行的第一列上的 I已確定，便第三章 有窮自動(dòng)機(jī) 6 b b a ? ? ? a b ? ? ? 0 1 2 5 3 4 6 7 8 9 10 ? ? 可根據(jù)前述定義求出這一行的第二、第三列上的 Ia 和 Ib。 ④ 將由上述過(guò)程得到的最終形式的表看作一個(gè)狀態(tài)轉(zhuǎn)換表，即把其中第一列中的元素作為狀態(tài)，把 Ia ,Ib分別看作是輸入符號(hào) a， b，把其余信息看作是狀態(tài)轉(zhuǎn)換函數(shù)之值。 解：構(gòu)造 M’狀態(tài)轉(zhuǎn)換表 a b [0,1,2,4,7] [1,2,3,4,6,7,8] [1,2,4,5,6,7] [1,2,3,4,6,7,8] [1,2,3,4,6,7,8] [1,2,4,5,6,7,9] [1,2,4,5,6,7] [1,2,3,4,6,7,8] [1,2,4,5,6,7] [1,2,4,5,6,7,9] [1,2,3,4,6,7,8] [1,2,4,5,6,7,10] [1,2,4,5,6,7,10] [1,2,3,4,6,7,8] [1,2,4,5,6,7] M’最終狀態(tài)轉(zhuǎn)換表 a b Q0 Q1 Q2 Q1 Q1 Q3 Q2 Q1 Q2 Q3 Q1 Q4 Q4 Q1 Q2 第三章 有窮自動(dòng)機(jī) 7 0 1 2 3 4 b b b b b a a a a a 0 1 S 0 S 1 S 5 0 S 1 S 2 S 7 1 S 2 S 2 S 5 1 S 3 S 5 S 7 0 S 4 S 5 S 6 0 S 5 S 3 S 1 0 S 6 S 8 S 0 1 S 7 S 0 S 1 1 S 8 S 0 S 6 0 0 1 S 0 S 1 S 5 0 S 1 S 2 S 7 1 S 2 S 2 S 5 1 S 3 S 5 S 7 0 S 5 S 3 S 1 0 S 6 S 8 S 0 1 S 7 S 0 S 1 1 S 8 S 0 S 6 0 0 1 S 0 S 1 S 5 0 S 1 S 2 S 7 1 S 2 S 2 S 5 1 S 3 S 5 S 7 0 S 5 S 3 S 1 0 S 7 S 0 S 1 1 二 、確定的有窮自動(dòng)機(jī)的化簡(jiǎn) 所謂一個(gè)確定的有窮自動(dòng)機(jī) M的化簡(jiǎn)是指： 尋找一個(gè)狀態(tài)數(shù)比 M少的 DFA M’， 使得 L(M)=L(M’ )，可通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。 DFA中，狀態(tài) s和 t等價(jià)的條件是： 一致性條件：狀態(tài) s和 t 必須同時(shí)為可接受狀態(tài) (終態(tài) )或不可接受狀態(tài) (非終態(tài) )。 對(duì) M的狀態(tài)集 S進(jìn)行劃分的步驟： ①把 S的終態(tài)與非終態(tài)分開(kāi)，分成兩個(gè)子集，形成基本劃分 Π，屬于這兩個(gè)不同子集的狀態(tài)是可區(qū)別的。 第三章 有窮自動(dòng)機(jī) 9 l q0 l, d q 1 l q1 l , d q 2 q 0 非 l ,d c h a r ch , n a m e [ k ] n a m e ? ?? re a d (c h ) q 0 若 c h = l n a m e ? n a m e + c h re a d (c h ) q 1 非 l,d 用 n a m e 查符號(hào)表，若沒(méi)有，則填表，否則返回其地址 re a d (c h ) q 2 若 c h = l o r d 三 、從化簡(jiǎn)后的 DFA到程序表示 識(shí)別標(biāo)識(shí)符的 DFA（圖 (a)）需改為圖 (b)所示狀態(tài)，其中， l代表字母， d代表數(shù)字。 一、從正規(guī)文法到 FA 設(shè)正規(guī)文法 G有形如 U→ aV(a?VT, V?VN或 V=ε )的產(chǎn)生式。構(gòu)造步驟如下： ① 自動(dòng)機(jī)每一個(gè)狀態(tài)的標(biāo)記，均作為正規(guī)文法的非終結(jié)符，其中，自動(dòng)機(jī)開(kāi)始狀態(tài)的標(biāo)記將作為正規(guī)文法的開(kāi)始符號(hào)。 一、正規(guī)表達(dá)式的操作符 連接 假定有兩個(gè)正規(guī)表達(dá)式 e1和 e2，它們分別產(chǎn)生語(yǔ)言 L1和 L2，于是定義正規(guī)表達(dá)式的連接操作為 e1?e2={x ?y|x?L1， y?L2} 其中 ?可省略 選擇 可用 |或 +表示，定義為 e1|e2={x |x?L1或 x?L2} 重復(fù) 用 *表示，表示 *中的表達(dá)式的 0次到若干次的自重復(fù)連接，即 e*={x| x?L1*} 例：正規(guī)表達(dá)式 110由數(shù)字 1， 1， 0連接在一起組成，且表示的語(yǔ)言為 L={110} 表達(dá)式 0|1所表示的語(yǔ)言為 L={0， 1} 表達(dá)式 1*所表示的語(yǔ)言為 L={1i|i=0， 1， 2...} 例：用正則表達(dá)式表示 {標(biāo)識(shí)符 }=字母 (字母 |數(shù)字 )* {實(shí)數(shù) }=((|+|)(數(shù)字 * .數(shù)字 數(shù)字 *) 二、正規(guī) 表達(dá)式的定義 所有正規(guī)表達(dá)式都可由下列規(guī)則構(gòu)造出來(lái)： ① ?是一個(gè)表示空集的正規(guī)表達(dá)式 ② ε 是一個(gè)正規(guī)表達(dá)式，它所表示的語(yǔ)言僅包含一個(gè)空符號(hào)串，即 {ε } ③ a是一個(gè)正規(guī)表達(dá)式， a?VT它所表示的語(yǔ)言（它所表示的正規(guī)集）是單個(gè)符號(hào) a所組成，即 {a} 第三章 有窮自動(dòng)機(jī) 11 ④如果 e1和 e2是正規(guī)表達(dá)式，其表示的語(yǔ)言分別為 L1和 L2， (e1 )|(e2)是一個(gè)表示語(yǔ)言 L1∪ L2的正規(guī)表達(dá)式 (e1 )((e2)是一個(gè)表示語(yǔ)言 L1L2的正規(guī)表達(dá)式 (e1 )*是一個(gè)表示語(yǔ)言 L1*的正規(guī)表達(dá)式 ⑤正規(guī)表達(dá)式中操作符的優(yōu)先級(jí)順序?yàn)? *，連 接， | 例：正規(guī)表達(dá)式 a*b*表示的正規(guī)集是 {ambn|m≥ 0,n≥ 0} 正規(guī)表達(dá)式 (ab)*表示的正規(guī)集是 {(ab)m|m≥ 0} 正規(guī)表達(dá)式 (a|b)*表示的正規(guī)集是 {x|x?{a,b}*} 表達(dá)式 (aa|ab|ba|bb)*表示在 VT={a,b}上的所有偶長(zhǎng)度的串 三、正規(guī)表達(dá)式的等價(jià)性 如果兩個(gè)正規(guī)表達(dá)式表示相同的語(yǔ)言，則這兩個(gè)正規(guī)表達(dá)式相等或等價(jià)，故有00*=000*|0 四、正規(guī)表達(dá)式的性質(zhì) r|s=s|r 或滿足交換律 r|(s|t)=(r|s)|t 或滿足結(jié)合律 (rs)t= r(st) 連接滿足結(jié)合律 r(s|t)=rs|rt (s|t)r=sr|tr 分配律 ε r=r， rε =r ε 是連接的恒等元素 例：程序設(shè)計(jì)語(yǔ)言中的單詞都能用正規(guī)式來(lái)定義，如： ∑ ={字母 ,數(shù)字 }上的正規(guī)式 e1=字母 (字母 |數(shù)字 )*表示的是所有標(biāo)識(shí)符的集合 正規(guī)式 e=dd*定義了無(wú)符號(hào)整數(shù) 令 ∑ ={d,.,e,+,}， 則 ∑ 上的正規(guī)式 (d*.dd*| dd*)(e(+||ε )dd*|ε )表示的是無(wú)符號(hào)數(shù)。 ③ 對(duì)已轉(zhuǎn)換的文法中的形如 A→ x*y的產(chǎn)生式，重 寫(xiě)為 A→ xA， A→ y 第三章 有窮自動(dòng)機(jī) 12 文法產(chǎn)生式 正規(guī)式 規(guī)則 1 A ? xB ,B ? y A=xy 規(guī)則 2 A ? xA | y A=x* y 規(guī)則 2 A ? x,|A ? y A=x|y A e1e2 B (a) A e 1 C e 2 B (b ) A e1?e2 B (c ) A B (d) e 1 e 2 ④ 對(duì)形如 A→ x|y的產(chǎn)生式重寫(xiě)為 A→ x， A→ y 不斷利用上述規(guī)則作變換，直到每個(gè)產(chǎn)生式最多含有一個(gè) VN為止。同一個(gè)語(yǔ)言，既可用FA描述，也可用正規(guī)表達(dá)式描述。 練習(xí)：構(gòu)造與 ∑ ={a,b}上的正規(guī)式 (a|b)*(aa|bb)(a|b)*等價(jià)的自動(dòng)機(jī)。修改后 ,構(gòu)成了一個(gè)新的 NFA，它只有一個(gè)初態(tài)結(jié)點(diǎn) S和一個(gè)終態(tài)結(jié)點(diǎn) Z，這個(gè)新的 NFA M′顯然和原 NFA M等價(jià)。 第三章 有窮自動(dòng)機(jī) 14 1