《有窮自動機(jī)》ppt課件

《《有窮自動機(jī)》ppt課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第三章有窮自動機(jī)本章介紹有關(guān)有窮自動機(jī)的基本概念和理論以及正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī)之間的相互關(guān)系。3.1概述——有窮自動機(jī)的意義有窮狀態(tài)自動機(jī)(Finite-stateAutomataFSA)或簡稱FA是具有離散的輸入輸出系統(tǒng)的數(shù)學(xué)模型。系統(tǒng)內(nèi)部具有有窮個狀態(tài)，系統(tǒng)的狀態(tài)概括了對過去輸入狀況的處理信息，系統(tǒng)只需根據(jù)當(dāng)前所處的狀態(tài)和面臨的輸入就可以決定系統(tǒng)的后繼行為，系統(tǒng)處理了當(dāng)前的輸入后，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生變化。電梯控制裝置、文本編輯程序、編譯技術(shù)中的詞法分析程序，計算機(jī)以及人腦都是有窮狀態(tài)系統(tǒng)。1-91,3,5,7,93.1

2、概述——有窮自動機(jī)的模型104397TAS1,3,5,7,9輸入帶有窮控制器讀頭0-93.2有窮自動機(jī)的形式定義定義3.1一個確定有窮自動機(jī)DFSA是一個五元組M=(Q,?,t,q0,F)其中，Q：是非空有窮狀態(tài)集,其中的每個元素稱為一個狀態(tài)；?：是有窮輸入字母表，它的每一個元素稱為一個輸入符號；t：是一個單值映射Q???Q，也稱狀態(tài)轉(zhuǎn)換函數(shù)，t(q,x)=q?意指：當(dāng)現(xiàn)行狀態(tài)為q，面臨的輸入符號為x時，將轉(zhuǎn)到下一狀態(tài)q?，q?稱為q的一個后繼狀態(tài)；q0?Q稱之為開始狀態(tài)；F?Q稱為終止?fàn)顟B(tài)集，至少由一個終止?fàn)顟B(tài)組成。3.2.1狀態(tài)轉(zhuǎn)換表（

3、矩陣）DFA轉(zhuǎn)換矩陣:該矩陣行表示狀態(tài)集；列表示輸入字母表；矩陣元素表示t（q,a）的值。即某行狀態(tài)面臨某列輸入字符所唯一轉(zhuǎn)向的下一個狀態(tài)。該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣3.2.1狀態(tài)轉(zhuǎn)換表（矩陣）例3.1有窮自動機(jī)A=(Q,?,t,q0,F)其中，Q={S,A,B,G,H}，?={+，-，·，d}，S是開始狀態(tài)，終止?fàn)顟B(tài)集F={B,H}，映射t:Q???Q由下表所示的狀態(tài)轉(zhuǎn)換表給出。符號狀態(tài)+-·dSAAGBAGBHBGHH3.2.2狀態(tài)轉(zhuǎn)換圖(1)一個DFA也可表示成一張狀態(tài)轉(zhuǎn)換圖。DFA狀態(tài)：用圓圈節(jié)點(diǎn)表示；初始狀態(tài)節(jié)點(diǎn)：用“右向雙(單)箭頭

4、”表示；終止?fàn)顟B(tài)節(jié)點(diǎn)：用“雙圈”表示；狀態(tài)變遷：用單向弧線表示，上面必須標(biāo)記激勵變遷的符號。3.2.2狀態(tài)轉(zhuǎn)換圖例3.2有窮自動機(jī)A(記為DFSAA)，A=(Q,?,t,q0,F)其中，Q={q0,q1,q2,q3}，?={a,b}，q0是開始狀態(tài)，終止?fàn)顟B(tài)集F={q0}，映射t:Q???Q由下圖所示的狀態(tài)轉(zhuǎn)換圖給出。在圖中，狀態(tài)q0用雙圓圈標(biāo)記，表明它是終止?fàn)顟B(tài)；同時，用一個箭頭標(biāo)記，表明它是開始狀態(tài)。3.2.3構(gòu)形和移動（1）對于一個給定的輸入串,假定一個DFSA已經(jīng)完成了若干次移動,為了預(yù)測它的進(jìn)一步行為,只需要知道”當(dāng)前狀態(tài)”和”尚

5、待掃描的輸入串”,這兩類信息對于在某一次的特定應(yīng)用中,位于某個特定時刻的DFSA提供了一種完整的描述,這種描述就稱為構(gòu)形。3.2.3構(gòu)形和移動（2）構(gòu)形(q0，ω)稱為初始構(gòu)形，其中q0是初始狀態(tài)，ω是由該自動機(jī)可接收或拒絕的任何輸入串。構(gòu)形(q,?)稱為終止構(gòu)形，其中?是空串，q?F(終態(tài)集)。自動機(jī)的移動(記為├)是從一種構(gòu)形到另一種構(gòu)形的轉(zhuǎn)換。DFSA的工作過程就是一系列的移動過程。記號├+稱為├的傳遞閉包；├*稱為├的自反閉包。├*表示“0次或多次移動”；├+表示“一次或多次移動”。3.2.3構(gòu)形和移動（3）DFSAM所識別的語言L

6、（M）可表示為：L（M）={ω??*︱（q0,ω)├*(q,?)＆q?F}自動機(jī)接受(識別)字符串1）自動機(jī)所接收字符如果對某一自動機(jī)M=（Q,?,t,q0,F）x∈?,有t（q0,x）=P,且P∈F，則稱字符x被自動機(jī)所接收。2）自動機(jī)所接收輸入串自動機(jī)從開始狀態(tài)讀完全部輸入串后，自動機(jī)恰好到達(dá)終止?fàn)顟B(tài)，則稱輸入串被自動機(jī)所接收。自動機(jī)接受(收)字符串3）自動機(jī)接收語言自動機(jī)M所能接收的串組成一個集合，則稱該集合為自動機(jī)M所能接收（識別）的語言。用L（M）表示：L（M）＝{ω∣t(q0,ω)∈F,ω∈?*}3.2.4自動機(jī)的等價性定義3.

7、2M和M?是等價的，當(dāng)且僅當(dāng)對每一個串x，M接收x當(dāng)且僅當(dāng)M?接收x。定義3.3如果M僅通過重新標(biāo)記它的狀態(tài)就能轉(zhuǎn)換稱M?,則M和M?稱為同構(gòu)的(Isomorphic)。FSA的一個基本定理是：對每一個自動機(jī)M，存在一個等價的具有最少狀態(tài)個數(shù)的自動機(jī)M?，而且對于每一個其狀態(tài)個數(shù)與M?相同且等價于M?的自動機(jī)M″,必是與M?同構(gòu)的。換句話說，M?在結(jié)構(gòu)上是唯一的。3.2.5非確定有窮狀態(tài)自動機(jī)定義3.4一個非確定有窮自動機(jī)NDFSA是一個五元組NDFSA=(Q,?,t,q0,F)其中，Q是一個非空有窮狀態(tài)集，?是一個非空有窮輸入字母集，映射

8、t為Q???Q的子集(即t是一個多值映射)，Q0?Q是開始狀態(tài)集，F(xiàn)?Q是終止?fàn)顟B(tài)集。同樣的，NDFSA也可以用狀態(tài)轉(zhuǎn)換表和狀態(tài)轉(zhuǎn)換圖表示。3.2.5非有窮狀態(tài)自動機(jī)非確定有窮自