版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第二章:詞法分析
NFA與自動(dòng)機(jī)的最小化內(nèi)容介紹非確定有限自動(dòng)機(jī)(NFA)的定義NFA到DFA的轉(zhuǎn)換自動(dòng)機(jī)的最小化自動(dòng)機(jī)的化簡(jiǎn)1.1非確定有限自動(dòng)機(jī)的定義非確定有限自動(dòng)機(jī)NFA為一個(gè)五元組(,S,S0,f,Z),其中:是一個(gè)有窮字母表,它的每個(gè)元素稱為一個(gè)輸入字符;S是狀態(tài)的集合,它的每個(gè)元素稱為一個(gè)狀態(tài);S0
S,是非確定有限自動(dòng)機(jī)的初始狀態(tài)集;f是一個(gè)從S×(∪{})到S的子集的映射,即S×(∪{})→2sZS,是一個(gè)終止?fàn)顟B(tài)集,又稱為接受狀態(tài)集1.2DFA和NFA的區(qū)別總結(jié)來(lái)看有3點(diǎn)區(qū)別一個(gè)狀態(tài)的不同輸出邊可以標(biāo)有相同符號(hào)允許有多個(gè)開始狀態(tài)允許有空邊1.3NFA的一些問(wèn)題NFA所能接受的串與DFA的定義是相同的實(shí)現(xiàn)起來(lái)很困難aa,b102aba2.1自動(dòng)機(jī)等價(jià)定義:設(shè)A1和A2是同一個(gè)字母表上的自動(dòng)機(jī),如果有L(A1)=L(A2),則稱A1和A2等價(jià)定理:對(duì)于每一個(gè)非確定自動(dòng)機(jī)A,存在一個(gè)確定自動(dòng)機(jī)A’,使得L(A)=L(A’)2.2NFA到DFA的轉(zhuǎn)換狀態(tài)集I的ε閉包:設(shè)I是NFAM狀態(tài)集的子集,定義I的ε閉包ε-CLOSURE(I)為:若q∈I,則q∈ε_(tái)CLOSURE(I).若q∈I,那么從q出發(fā)經(jīng)任意條ε弧而能到達(dá)的任何狀態(tài)q'都屬于ε-CLOSURE(I).2.2NFA到DFA的轉(zhuǎn)換狀態(tài)集I的a轉(zhuǎn)換:若I={S1,…,Sm}是NFA的狀態(tài)集的一個(gè)子集,a∈,則定義:Ia=ε-CLOSURE(J)其中:J=f(S1,a)f(S2,a)…f(Sm,a)2.2NFA到DFA的轉(zhuǎn)換已知A:NFA,構(gòu)造A':DFA令A(yù)'的初始狀態(tài)為I0'=_CLOSURE({S1,S2,…Sk}),其中S1…Sk是A的全部初始狀態(tài)。若I={S1,…,Sm}是A'的一個(gè)狀態(tài),a,則定義f'(I,a)=Ia將Ia加入S',重復(fù)該過(guò)程,直到S'不產(chǎn)生新狀態(tài)。若I'={S1,…,Sn}是A'的一個(gè)狀態(tài),且存在一個(gè)Si是A的終止?fàn)顟B(tài),則令I(lǐng)'為A'的終止?fàn)顟B(tài)。2.2NFA到DFA的轉(zhuǎn)換a219b45aa38bba67例子:2.2NFA到DFA的轉(zhuǎn)換
輸入字
狀態(tài)ab+{1,2}{2,4,5,6,7}{3,8}-{2,4,5,6,7}{}{3,8,9}{3,8}{9}{}-{3,8,9}{9}{}-{9}{}{}2.2NFA到DFA的轉(zhuǎn)換轉(zhuǎn)化后的結(jié)果{1,2}對(duì)應(yīng)1{2,4,5,6,7}對(duì)應(yīng)2{3,8}對(duì)應(yīng)3{3,8,9}對(duì)應(yīng)4{9}對(duì)應(yīng)513245babaa2.2NFA到DFA的轉(zhuǎn)換另外一種消除空邊的轉(zhuǎn)換方式刪去空邊,增加0到2的邊ε環(huán)路的時(shí)候,就把這幾個(gè)狀態(tài)合成一個(gè)a10a2aa10a22.3自動(dòng)機(jī)的最小化定義:等價(jià)狀態(tài)
設(shè)DFAM的兩個(gè)狀態(tài)S1和S2,如果對(duì)任意輸入的符號(hào)串x,從S1和S2出發(fā),總是同時(shí)到達(dá)接受狀態(tài)或拒絕狀態(tài)中,則稱S1和S2是等價(jià)的。1234567abccbd2.3自動(dòng)機(jī)的最小化定義:無(wú)關(guān)狀態(tài)設(shè)S是DFAM的一個(gè)狀態(tài),若:從開始狀態(tài)無(wú)到S的通路,或S到任意終止?fàn)顟B(tài)無(wú)通路則稱S為M的無(wú)關(guān)狀態(tài)
102ab102ab2.3自動(dòng)機(jī)的最小化定義:最小(最簡(jiǎn))自動(dòng)機(jī)如果DFAM沒(méi)有無(wú)關(guān)狀態(tài),也沒(méi)有等價(jià)狀態(tài),則稱M為最小自動(dòng)機(jī)結(jié)論:任一DFA都可以化為最簡(jiǎn)自動(dòng)機(jī),即任一DFAM都存在DFAM',使得L(M)=L(M'),且M'是最簡(jiǎn)自動(dòng)機(jī)
2.4自動(dòng)機(jī)的化簡(jiǎn)狀態(tài)分離法終止?fàn)顟B(tài)為一組,非終止?fàn)顟B(tài)為一組對(duì)每一組進(jìn)行分離,若每組中的元素映射到不同的組,則表示他們不等價(jià),就可以劃分出來(lái)。重復(fù)2,知道沒(méi)有新組產(chǎn)生,此時(shí)每組中的狀態(tài)都為等價(jià)狀態(tài)。2.4自動(dòng)機(jī)的化簡(jiǎn)例1aa17b32bab5abaa46bb8bab2.4自動(dòng)機(jī)的化簡(jiǎn)1,3ba4,6,7,8a2,5bb2.4自動(dòng)機(jī)的化簡(jiǎn)例2a15
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025河南建筑安全員-A證考試題庫(kù)附答案
- 貴州大學(xué)《醫(yī)學(xué)統(tǒng)計(jì)學(xué)規(guī)培》2023-2024學(xué)年第一學(xué)期期末試卷
- 貴州財(cái)經(jīng)職業(yè)學(xué)院《火災(zāi)動(dòng)力學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 2025福建建筑安全員考試題庫(kù)
- 貴陽(yáng)學(xué)院《保險(xiǎn)投資學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 硅湖職業(yè)技術(shù)學(xué)院《植物造景技術(shù)(一)》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣州幼兒師范高等??茖W(xué)校《無(wú)人機(jī)結(jié)構(gòu)與系統(tǒng)》2023-2024學(xué)年第一學(xué)期期末試卷
- 2025年貴州省安全員B證考試題庫(kù)及答案
- 2025江蘇建筑安全員《B證》考試題庫(kù)及答案
- 2025年河南省安全員《C證》考試題庫(kù)及答案
- 工程機(jī)械租賃服務(wù)方案及保障措施范本
- SCI論文寫作課件
- 封條模板A4直接打印版
- 振動(dòng)篩使用說(shuō)明書..(共10頁(yè))
- (完整版)展廳展館博物館美術(shù)館設(shè)計(jì)標(biāo)招標(biāo)評(píng)分細(xì)則及打分表
- [宋小寶小品甄嬛后傳臺(tái)詞]甄嬛歪傳小品劇本臺(tái)詞范本
- 扭扭棒手工PPT課件
- 曲式分析演唱技巧情感運(yùn)用
- 古建筑白蟻危害及防控現(xiàn)狀
- 建筑裝飾裝修施工組織設(shè)計(jì)方案(完整版)
- 【設(shè)計(jì)】醫(yī)用棉簽卷棉機(jī)設(shè)計(jì)方案與分析報(bào)告(精華版)
評(píng)論
0/150
提交評(píng)論