形式語(yǔ)言與自動(dòng)機(jī)-5-dfa與nfa等價(jià)性及正則運(yùn)算封閉性(編輯修改稿)
2024-09-01 20:02 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 畢。UJS* 11n 說(shuō)明：說(shuō)明：– 上述證明使用的構(gòu)造較為簡(jiǎn)單，可以比較顯上述證明使用的構(gòu)造較為簡(jiǎn)單，可以比較顯然的觀察到其正確性。然的觀察到其正確性。– 對(duì)于更復(fù)雜的構(gòu)造，需要證明它是否如所聲對(duì)于更復(fù)雜的構(gòu)造，需要證明它是否如所聲稱的那樣工作。稱的那樣工作。– 通常這種證明采用對(duì)計(jì)算的步數(shù)做歸納的方通常這種證明采用對(duì)計(jì)算的步數(shù)做歸納的方式進(jìn)行，后面將給一個(gè)這樣的例子。式進(jìn)行，后面將給一個(gè)這樣的例子。UJS* 12n 推論推論 ：一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)由：一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)由一臺(tái)非確定型有限狀態(tài)自動(dòng)機(jī)識(shí)別它。一臺(tái)非確定型有限狀態(tài)自動(dòng)機(jī)識(shí)別它。n 例題例題 1：用前面例子上的機(jī)器：用前面例子上的機(jī)器 N4來(lái)說(shuō)明把來(lái)說(shuō)明把NFA轉(zhuǎn)換成轉(zhuǎn)換成 DFA的過(guò)程。的過(guò)程。UJS* 13N4 = {{1,2,3},{a,b},δ,1,{1}}n {1,2,3}為為 3個(gè)元素的狀態(tài)集，所以相應(yīng)的個(gè)元素的狀態(tài)集，所以相應(yīng)的 DFA的狀態(tài)集有的狀態(tài)集有 23個(gè)元素個(gè)元素n 空集，空集， {1}, {2}, {3}, {1,2},{1,3},{2,3},{1,2,3}n 相應(yīng)相應(yīng) DFA的起始狀態(tài)的起始狀態(tài) E({1}), 表示狀態(tài)表示狀態(tài) 1本身加本身加上由上由 1出發(fā)通過(guò)出發(fā)通過(guò) ε箭頭能到達(dá)的所有狀態(tài)箭頭能到達(dá)的所有狀態(tài)n 相應(yīng)相應(yīng) DFA的接受狀態(tài)是上述狀態(tài)中所有包含的接受狀態(tài)是上述狀態(tài)中所有包含 N4接受狀態(tài)接受狀態(tài) 1的狀態(tài)子集。的狀態(tài)子集。n {1},{1,2},{1,3},{1,2,3}n 相應(yīng)相應(yīng) DFA的轉(zhuǎn)移函數(shù)的轉(zhuǎn)移函數(shù) ———— 每一個(gè)狀態(tài)遇到輸入每一個(gè)狀態(tài)遇到輸入a到一個(gè)地方，遇到輸入到一個(gè)地方，遇到輸入 b到一個(gè)地方。到一個(gè)地方。UJS* 14可以簡(jiǎn)化這臺(tái)機(jī)器 , 刪掉沒(méi)有箭頭射入的兩個(gè)狀態(tài)： {1},{1, 2}UJS* 15n 重新排列：重新排列：UJS* 16第五章第五章 DFA與與 NFA等價(jià)性等價(jià)性及正則運(yùn)算封閉性及正則運(yùn)算封閉性n NFA 與與 DFA的等價(jià)性的等價(jià)性n 正則語(yǔ)言類在正則運(yùn)算下的封閉性正則語(yǔ)言類在正則運(yùn)算下的封閉性– – 連接運(yùn)算下的封閉性連接運(yùn)算下的封閉性– 星號(hào)運(yùn)算下的封閉性星號(hào)運(yùn)算下的封閉性UJS* 17n 前面已經(jīng)說(shuō)過(guò)，正則語(yǔ)言在正則運(yùn)算下前面已經(jīng)說(shuō)過(guò)，正則語(yǔ)言在正則運(yùn)算下是封閉的。正則運(yùn)算有三個(gè)運(yùn)算：并運(yùn)是封閉的。正則運(yùn)算有三個(gè)運(yùn)算：并運(yùn)算、連接運(yùn)算以及星號(hào)運(yùn)算。我們僅完算、連接運(yùn)算以及星號(hào)運(yùn)算。我們僅完成了并運(yùn)算的證明，而放棄了連接運(yùn)算成了并運(yùn)算的證明，而放棄了連接運(yùn)算封閉性的證明，因?yàn)樘珡?fù)雜。封閉性的證明，因?yàn)樘珡?fù)雜。n 有了非確定性，能讓證明容易多了。有了非確定性，能讓證明容易多了。UJS* 18第五章第五章 DFA與
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1