形式語(yǔ)言與自動(dòng)機(jī)-4-非確定性與NFA課件

9/7/20239:46AM1第四章非確定性與NFA確定型計(jì)算——計(jì)算的每一步都按照唯一的方式跟在前一步的后面。當(dāng)自動(dòng)機(jī)處于給定的狀態(tài)讀下一個(gè)輸入符號(hào)時(shí)，機(jī)器的下一個(gè)狀態(tài)是確定的。非確定型自動(dòng)機(jī)中，在任何一點(diǎn)，下一個(gè)狀態(tài)可能存在若干個(gè)選擇。非確定型自動(dòng)機(jī)是確定型自動(dòng)機(jī)的推廣，因此任何確定型自動(dòng)機(jī)(DFA)都是一臺(tái)非確定型自動(dòng)機(jī)(NFA)，此外，非確定型自動(dòng)機(jī)應(yīng)該有一些另外的性質(zhì)。8/3/20232:24PMwww.kmitwan.co19/7/20239:46AM2第四章非確定性與NFA4.1非確定型有窮自動(dòng)機(jī)4.1.1NFA引例4.1.2NFA的計(jì)算 4.1.3NFA的例子4.2NFA的形式定義 4.2.1NFA的形式定義 4.2.2NFA計(jì)算的形式定義8/3/20232:24PMwww.kmitwan.co29/7/20239:46AM3NFA與DFA的區(qū)別：DFA的每一個(gè)狀態(tài)恰好有一個(gè)轉(zhuǎn)移箭頭射出；而NFA在同一狀態(tài)對(duì)同一輸入可能有0個(gè),1個(gè)，甚至多個(gè)箭頭射出。譬如：N1中q1狀態(tài)下對(duì)1有2個(gè)輸出，而q2狀態(tài)對(duì)1沒(méi)有輸出。DFA的箭頭標(biāo)記符號(hào)都來(lái)自字母表；NFA中允許空字符ε，甚至允許射出0個(gè),1個(gè)，或者多個(gè)箭頭帶ε的箭頭射出。8/3/20232:24PMwww.kmitwan.co39/7/20239:46AM4第四章非確定性與NFA4.1非確定型有窮自動(dòng)機(jī)4.1.1NFA引例4.1.2NFA的計(jì)算 4.1.3NFA的例子4.2NFA的形式定義 4.2.1NFA的形式定義 4.2.2NFA計(jì)算的形式定義8/3/20232:24PMwww.kmitwan.co49/7/20239:46AM5三類(lèi)看法：機(jī)器分裂論并行計(jì)算論可能性樹(shù)”8/3/20232:24PMwww.kmitwan.co59/7/20239:46AM6機(jī)器分裂論如：N1中，在q1狀態(tài)輸入1時(shí)，機(jī)器把自己裂成兩個(gè)備份，并且每一個(gè)備份都并行地執(zhí)行下去。N1中，在q3狀態(tài)輸入0時(shí)，輸入符號(hào)不在任何射出的箭頭上，則找個(gè)機(jī)器備份及其關(guān)聯(lián)的計(jì)算分支一塊死掉。如果機(jī)器的某一個(gè)備份在輸入的末端在接受狀態(tài)，則這臺(tái)NFA接受輸入串。如果遇到ε，不用讀任何輸入，機(jī)器分裂成多個(gè)備份，每一個(gè)標(biāo)記ε的箭頭有一個(gè)備份跟蹤，還有一個(gè)停留在當(dāng)前狀態(tài)。8/3/20232:24PMwww.kmitwan.co69/7/20239:46AM7并行計(jì)算論非確定性可以看作若干過(guò)程能同時(shí)運(yùn)行的一類(lèi)并行計(jì)算。當(dāng)NFA分頭跟蹤若干選擇時(shí)，這對(duì)應(yīng)于一個(gè)過(guò)程“分叉”成若干子過(guò)程，各個(gè)子過(guò)程分別進(jìn)行。如果這些子過(guò)程中至少有一個(gè)接受，則整個(gè)計(jì)算接受?！翱赡苄詷?shù)”樹(shù)根對(duì)應(yīng)計(jì)算的開(kāi)始，樹(shù)中的每一個(gè)分支點(diǎn)對(duì)應(yīng)計(jì)算中機(jī)器有多種選擇的點(diǎn)。如果計(jì)算中至少有一個(gè)分支結(jié)束在接受狀態(tài)，則機(jī)器接受。8/3/20232:24PMwww.kmitwan.co79/7/20239:46AM8例題1：對(duì)非確定型有窮狀態(tài)自動(dòng)機(jī)N1輸入串010110。8/3/20232:24PMwww.kmitwan.co89/7/20239:46AM98/3/20232:24PMwww.kmitwan.co99/7/20239:46AM10手指記憶法：用手指按住狀態(tài)圖中的狀態(tài)，表示當(dāng)前所處的狀態(tài)，并行多個(gè)狀態(tài)用多個(gè)手指表示，上圖中最多時(shí)同時(shí)需要用5個(gè)手指頭。嘗試用手指頭記憶的方式來(lái)試驗(yàn)，確認(rèn)一下N1是否接受含有101或11作為子串的所有字符串。8/3/20232:24PMwww.kmitwan.co109/7/20239:46AM11非確定型有窮狀態(tài)自動(dòng)機(jī)在以下幾個(gè)方面是有用的：每一臺(tái)NFA可以轉(zhuǎn)換成一臺(tái)等價(jià)DFA，構(gòu)造NFA有時(shí)比直接構(gòu)造DFA容易，一臺(tái)NFA可能比等價(jià)的DFA小得多或功能更容易理解有窮自動(dòng)機(jī)特別容易理解，有窮自動(dòng)機(jī)的非確定性也是對(duì)能力更強(qiáng)的計(jì)算模型的非確定性的一個(gè)很好引入。8/3/20232:24PMwww.kmitwan.co119/7/20239:46AM12第四章非確定性與NFA4.1非確定型有窮自動(dòng)機(jī)4.1.1NFA引例4.1.2NFA的計(jì)算

4.1.3NFA的例子4.2NFA的形式定義 4.2.1NFA的形式定義 4.2.2NFA計(jì)算的形式定義8/3/20232:24PMwww.kmitwan.co129/7/20239:46AM13例題2：設(shè)A是{0,1}上倒數(shù)第3個(gè)符號(hào)為1的所有字符串組成的語(yǔ)言，設(shè)計(jì)識(shí)別A的自動(dòng)機(jī)。8/3/20232:24PMwww.kmitwan.co139/7/20239:46AM148/3/20232:24PMwww.kmitwan.co149/7/20239:46AM15注意：描述N2的最小的DFA，需要8個(gè)狀態(tài)對(duì)應(yīng)的DFA有助于我們理解N2思考題：下圖是N2的一個(gè)修改，用樹(shù)型圖轉(zhuǎn)化一下，看看它識(shí)別什么語(yǔ)言？構(gòu)建的其對(duì)應(yīng)的DFA？8/3/20232:24PMwww.kmitwan.co159/7/20239:46AM16例題3：考慮NFA—N3，它的輸入字母表{0}由一個(gè)符號(hào)組成。8/3/20232:24PMwww.kmitwan.co169/7/20239:46AM17N3表示所有形如0k的字符串，其中k是2或者3的倍數(shù)。可接受空串，00，000，但是不能接受0和00000。使用ε讓該自動(dòng)機(jī)最容易理解，當(dāng)然，N3可以用DFA表示，不過(guò)理解上不夠直觀。8/3/20232:24PMwww.kmitwan.co179/7/20239:46AM18例題4：考慮NFA—N4，它的輸入字母表為{a,b}，考察N4所能識(shí)別的語(yǔ)言。N4能識(shí)別ε，a,baba和baa,而不接受b,bb,babba。思考，如何將這個(gè)NFA轉(zhuǎn)化為DFA8/3/20232:24PMwww.kmitwan.co189/7/20239:46AM19第四章非確定性與NFA4.1非確定型有窮自動(dòng)機(jī)4.1.1NFA引例4.1.2NFA的計(jì)算 4.1.3NFA的例子4.2NFA的形式定義

4.2.1NFA的形式定義 4.2.2NFA計(jì)算的形式定義8/3/20232:24PMwww.kmitwan.co199/7/20239:46AM20FA和DFA很多地方類(lèi)似，其本質(zhì)的不同存在于轉(zhuǎn)移函數(shù)。DFA中，轉(zhuǎn)移函數(shù)取一個(gè)狀態(tài)和一個(gè)輸入符號(hào)，產(chǎn)生下一個(gè)狀態(tài)。NFA中，轉(zhuǎn)移函數(shù)取一個(gè)狀態(tài)和一個(gè)輸入符號(hào)或空串，產(chǎn)生可能的下一個(gè)狀態(tài)的集合。8/3/20232:24PMwww.kmitwan.co209/7/20239:46AM21第四章非確定性與NFA4.1非確定型有窮自動(dòng)機(jī)4.1.1NFA引例4.1.2NFA的計(jì)算 4.1.3NFA的例子4.2NFA的形式定義

4.2.1NFA的形式定義

4.2.2NFA計(jì)算的形式定義8/3/20232:24PMwww.kmitwan.co219/7/20239:46AM22定義：非確定型有窮自動(dòng)機(jī)是一個(gè)5元組(Q,∑,δ,q0,F)，其中Q是一個(gè)有窮狀態(tài)集；∑是一個(gè)有窮字母表；δ:Q×∑ε→P(Q)是一個(gè)轉(zhuǎn)移函數(shù)q0

∈Q是起始狀態(tài)F屬于Q是接受狀態(tài)集。說(shuō)明：定義中∑ε

=∑∪{ε}，P(Q)表示Q的冪集，是Q的所有子集組成的集合。8/3/20232:24PMwww.kmitwan.co229/7/20239:46AM23例題5：N1的形式化描述8/3/20232:24PMwww.kmitwan.co239/7/20239:46AM24N1=(Q,∑,δ,q1,F)Q={q1,q2,q3,q4}；∑={0,1}；δ如表所示q1

∈Q是起始狀態(tài)F={q4}。01εq1

{q1}{q1,q2}Φq2{q3}Φ{q3}q3Φ{q4}Φq4{q4}{q4}Φ8/3/20232:24PMwww.kmitwan.co249/7/20239:46AM25第四章非確定性與NFA4.1非確定型有窮自動(dòng)機(jī)4.1.1NFA引例4.1.2NFA的計(jì)算 4.1.3NFA的例子4.2NFA的形式定義 4.2.1NFA的形式定義

4.2.2NFA計(jì)算的形式定義8/3/20232:24PMwww.kmitwan.co259/7/20239:46AM26定義2：設(shè)N=(Q,∑,δ,q0,F)是一臺(tái)NFA，ω是字母表∑上的一個(gè)字符,如果把ω寫(xiě)成ω=y1y2…ym，其中yi是∑ε的成員。如果存在Q中的狀態(tài)序列r0，r1，r2，…，rm，滿(mǎn)足下述條件：(1)r0=q0(2)ri+1∈δ(ri,yi+1),i=0,1,…,m-1(3)rn∈F則N接受ω。8/3/20232:24PMwww.k