資源描述：
《形式語言與自動機_有窮自動機》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、1形式語言與自動機第三章有窮自動機南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院胡軍hujun.nju@139.com31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍2第三章有窮自動機1.1非形式化描述1.2有窮自動機的基本定義1.3非確定的有窮自動機1.4具有ε轉(zhuǎn)移的有窮自動機1.5有窮自動機的應(yīng)用1.6具有輸出的有窮自動機（*)31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍31.1有窮狀態(tài)系統(tǒng)指針式鐘表共有12*60*60個狀態(tài)小時×分鐘×秒圍棋共有3361個狀態(tài)每一個格子：（空，黑，白）；格子數(shù)量：19行×19列某些電子產(chǎn)品中的開關(guān)電路，具有n個門的
2、開關(guān)網(wǎng)絡(luò)有2n種狀態(tài)“網(wǎng)上購物”系統(tǒng)（示例：）31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍42007年圖靈獎模型檢驗（modelchecking）:基于自動機理論的形式化方法(formalmethods)E.ClarkEmersonSifakis31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍51.2有窮自動機的基本定義定義3.1一個有窮自動機(FiniteAutomata)簡稱FA，是一個五元組：M=(Q,∑,δ,q0,F)，其中（1）Q是有窮狀態(tài)集；（States）（2）∑是有窮的輸入字母表（Alphabet）（3）δ是轉(zhuǎn)移函數(shù)，它將Q×∑
3、→Q(全映射)；（Transistonfunction）（4）q0∈Q，是初始狀態(tài)；（Initialstate）（5）FQ，是終結(jié)狀態(tài)集。（Acceptingstates）(終止狀態(tài)，接受狀態(tài))上述定義的另一個說法：確定型的有窮自動機(DeterministicFiniteAutomata：DFA)31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍6DFA例子q0q1q21000,11字母表：S={0,1}狀態(tài)集：Q={q0,q1,q2}初始狀態(tài)：q0終結(jié)狀態(tài):F={q0,q1}狀態(tài)集輸入01q0q1q2q0q1q2q2q2q1轉(zhuǎn)換函數(shù)表d:**→
4、問題：1.接受什么特征的字符串？2.狀態(tài)q2起什么作用？31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍7這兩個DFA所接受的字符串集合分別是什么？DFA例子q0q1baabS={a,b}q0q1q2q3q4aaaaabbbbbS={a,b}31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍8設(shè)計一個DFA(字母表為{0,1}),接受如下字符串：設(shè)計一個DFA(字母表為{0,1}),接受如下特征的字符串：最多有三個1.q0q1011q20q31q4+0,1010DFA例子L={010,1}qeq0q1q01q010qdie0,10100,11010,
5、131七月2021南京航空航天大學(xué)計算機學(xué)院胡軍9設(shè)計一個DFA(字母表為{0,1}),接受所有結(jié)尾是01的字符串。提示：DFA得記住讀入字符串的最后兩位。DFA例子qe01q0q1q00q10q01q110101001110031七月2021南京航空航天大學(xué)計算機學(xué)院胡軍10設(shè)計一個DFA(字母表為{0,1}),接受所有結(jié)尾是101的字符串。DFA例子31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍11例3.1給出一個有窮自動機Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0})其中：轉(zhuǎn)移函數(shù)δ具體定義如下：δ(q0,1)=q1δ
6、(q0,0)=q2δ(q1,1)=q0δ(q1,0)=q3δ(q2,1)=q3δ(q2,0)=q0δ(q3,1)=q2δ(q3,0)=q1→*DFA例子31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍12有窮自動機的擴充定義定義3.2對于有窮自動機M=(Q，∑，δ，q0，F(xiàn))，它的擴充轉(zhuǎn)移函數(shù),是從Q×∑*到Q的映射，其具體定義如下：（1）(q,ε)=q；（2）(q,wa)=δ((q,w),a)。其中q∈Q，w∈∑*，a∈∑。例如，對于例3.1中的有窮自動機，就有：(q0,010)=δ((q0,01),0)=δ(δ((q0,0),1),0)=δ(
7、δ(δ((q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q2,1),0)=δ(q3,0)=q1。31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍13有窮自動機的基本定義從δ到的擴充是很自然的，δ就是的特例（當
8、x
9、=1時）。今后在提到FA的轉(zhuǎn)移函數(shù)時，不再強調(diào)這種寫法，一律用δ表示，即δ的第二個變元既可以是單個字符也可以是一個字符串。31七月2021南京航空航天大學(xué)計算機學(xué)院胡軍14有窮自動機模型開始時，“讀頭”指向帶上的第一個輸入符號，控制器中放的是FA的初始狀態(tài)。然后，依據(jù)轉(zhuǎn)移函數(shù)δ做動作：若控制器中的當前狀態(tài)是q
10、，且“讀頭”指向帶上符號為a，則控制器中狀態(tài)將變成p=δ(q,a)，且“讀頭”向右移指向帶上下一個符號，如此可以繼續(xù)進行下去。(注意：讀頭不能回頭，只
