從正則表達(dá)式到有限自動(dòng)機(jī)

從正則表達(dá)式到有限自動(dòng)機(jī)

3.7~3.9目前一頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)有限自動(dòng)機(jī)目前二頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3

有限自動(dòng)機(jī)

3.3.1不確定的有限自動(dòng)機(jī)（簡(jiǎn)稱NFA） 一個(gè)數(shù)學(xué)模型，它包括：

1、有限的狀態(tài)集合S

2、輸入符號(hào)集合

3、轉(zhuǎn)換函數(shù)move:S({})

P(S)

4、狀態(tài)s0是唯一的開(kāi)始狀態(tài)

5、F

S是接受狀態(tài)集合識(shí)別語(yǔ)言(a|b)*ab

的NFA12開(kāi)始a0abb一個(gè)符號(hào)標(biāo)記離開(kāi)同一狀態(tài)有多條邊目前三頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)ab0{0,1}{0}1{2}2狀態(tài)

NFA的轉(zhuǎn)換表3.3有限自動(dòng)機(jī)

識(shí)別語(yǔ)言(a|b)*ab

的NFA12開(kāi)始a0abb目前四頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3.2確定的有限自動(dòng)機(jī)（簡(jiǎn)稱DFA)

一個(gè)數(shù)學(xué)模型，包括：1、有限的狀態(tài)集合S2、輸入字母集合3、轉(zhuǎn)換函數(shù)move:SS，且可以是部分函數(shù)4、唯一的開(kāi)始狀態(tài)s05、接受狀態(tài)集合FS12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

的DFA3.3有限自動(dòng)機(jī)

一個(gè)符號(hào)標(biāo)記離開(kāi)同一狀態(tài)只有一條邊目前五頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3有限自動(dòng)機(jī)

例識(shí)別(a|b)*a

b的DFA

DFANFA目前六頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)NFA到DFA——子集構(gòu)造法目前七頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3.3NFA到DFA的變換

子集構(gòu)造法 1、DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合

2、讀了輸入a1a2…an后，

NFA能到達(dá)的所有狀態(tài)：s1,s2,…,sk，則

DFA到達(dá)狀態(tài){s1,s2,…,sk}12a開(kāi)始0abb{0}{0,1}aba{0,2}b3.3有限自動(dòng)機(jī)

未畫完目前八頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3有限自動(dòng)機(jī)

3.3.3NFA到DFA的變換

子集構(gòu)造法目前九頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)子集構(gòu)造法ε-closure(s)從NFA的狀態(tài)S出發(fā)，只用ε轉(zhuǎn)換就能到達(dá)的狀態(tài)的集合ε-closure(T)從NFA的狀態(tài)集合T中每個(gè)狀態(tài)出發(fā)，只用ε轉(zhuǎn)換就能到達(dá)的狀態(tài)的集合Move(T,a)

狀態(tài)集合T中每個(gè)狀態(tài)通過(guò)a能到達(dá)的所有狀態(tài)集合19開(kāi)始0abab6782345目前十頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)子集構(gòu)造法找出U=ε-closure(T)對(duì)于U，以及任意符號(hào)a，找出U通過(guò)a能到達(dá)的集合V=Move(U,a)，并計(jì)算V'=ε-closure(V)U通過(guò)a到達(dá)的狀態(tài)即為V'，U-a->V'19開(kāi)始0abab6782345目前十一頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3有限自動(dòng)機(jī)

3.3.3NFA到DFA的變換

子集構(gòu)造法：狀態(tài)轉(zhuǎn)換表的構(gòu)造目前十二頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)

例 (a|b)*ab，NFA如下，把它變換為DFA3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前十三頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)ab狀態(tài)

3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前十四頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abA狀態(tài)

A={0,1,2,4,7}

3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前十五頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)19開(kāi)始0abab6782345輸入符號(hào)abAB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}

3.3有限自動(dòng)機(jī)

目前十六頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前十七頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}

3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前十八頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前十九頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCBBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前二十頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCBBDC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前二十一頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCBBDCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前二十二頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCBBDCBCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前二十三頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCBBDCBCDBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前二十四頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)輸入符號(hào)abABCBBDCBCDBC狀態(tài)

BD開(kāi)始aAabbabCba3.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345目前二十五頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)19開(kāi)始0abab6782345BD開(kāi)始aAabbabCba12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

的自動(dòng)機(jī)3.3有限自動(dòng)機(jī)

目前二十六頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)19開(kāi)始0abab6782345BD開(kāi)始aAabbabCba12開(kāi)始a0abbab子集構(gòu)造法不一定得到最簡(jiǎn)DFA3.3有限自動(dòng)機(jī)

識(shí)別語(yǔ)言(a|b)*ab

的自動(dòng)機(jī)目前二十七頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)DFA的化簡(jiǎn)目前二十八頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3.4DFA的化簡(jiǎn)構(gòu)造最簡(jiǎn)DFA：構(gòu)造狀態(tài)集合的初始劃分π：兩個(gè)子集——接受狀態(tài)子集F和非接受狀態(tài)子集S–F3.3有限自動(dòng)機(jī)

目前二十九頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3.4DFA的化簡(jiǎn)構(gòu)造最簡(jiǎn)DFA：構(gòu)造狀態(tài)集合的初始劃分π：兩個(gè)子集——接受狀態(tài)子集F和非接受狀態(tài)子集S–F應(yīng)用下面的過(guò)程構(gòu)造πnewForπ

中的每個(gè)子集G，dobegin把G劃分為若干子集，G的兩個(gè)狀態(tài)s和t在同一子集中，當(dāng)且僅當(dāng)對(duì)任意輸入符號(hào)a，s和t的a轉(zhuǎn)換都到π

的同一子集中在πnew中，用G的劃分代替GEnd3.3有限自動(dòng)機(jī)

目前三十頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3.4DFA的化簡(jiǎn)構(gòu)造最簡(jiǎn)DFA：構(gòu)造狀態(tài)集合的初始劃分π：兩個(gè)子集——接受狀態(tài)子集F和非接受狀態(tài)子集S–F應(yīng)用下面的過(guò)程構(gòu)造πnewForπ

中的每個(gè)子集G，dobegin把G劃分為若干子集，G的兩個(gè)狀態(tài)s和t在同一子集中，當(dāng)且僅當(dāng)對(duì)任意輸入符號(hào)a，s和t的a轉(zhuǎn)換都到π

的同一子集中在πnew中，用G的劃分代替GEnd如果πnew=π，則πfinal=π；否則令π=πnew

，轉(zhuǎn)上步3.3有限自動(dòng)機(jī)

目前三十一頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.3.4DFA的化簡(jiǎn)構(gòu)造最簡(jiǎn)DFA：構(gòu)造狀態(tài)集合的初始劃分π：兩個(gè)子集——接受狀態(tài)子集F和非接受狀態(tài)子集S–F應(yīng)用下面的過(guò)程構(gòu)造πnewForπ

中的每個(gè)子集G，dobegin把G劃分為若干子集，G的兩個(gè)狀態(tài)s和t在同一子集中，當(dāng)且僅當(dāng)對(duì)任意輸入符號(hào)a，s和t的a轉(zhuǎn)換都到π

的同一子集中在πnew中，用G的劃分代替GEnd如果πnew=π，則πfinal=π；否則令π=πnew

，轉(zhuǎn)上步在πfinal的每個(gè)狀態(tài)子集中選一個(gè)狀態(tài)代表它，即為最簡(jiǎn)DFA的狀態(tài)3.3有限自動(dòng)機(jī)

目前三十二頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)DFA的化簡(jiǎn)把G劃分為若干子集，G的兩個(gè)狀態(tài)s和t在同一子集中，當(dāng)且僅當(dāng)對(duì)任意輸入符號(hào)a，s和t的a轉(zhuǎn)換都到同一子集中目前三十三頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)DFA的化簡(jiǎn)構(gòu)造最簡(jiǎn)的DFA接受狀態(tài)子集{D},非接受狀態(tài)子集{A,B,C}{A,B,C}->{A,C}{B}BD開(kāi)始aAabbabCba目前三十四頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)從正則表達(dá)式到有限自動(dòng)機(jī)目前三十五頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)從正則式建立識(shí)別器的步驟從正則式構(gòu)造NFA（本節(jié)介紹）用語(yǔ)法制導(dǎo)的算法，它用正則式語(yǔ)法結(jié)構(gòu)來(lái)指導(dǎo)構(gòu)造過(guò)程把NFA變成DFA（子集構(gòu)造法，已介紹）將DFA化簡(jiǎn)（合并不可區(qū)別狀態(tài)，也已介紹）3.4從正則式到有限自動(dòng)機(jī)目前三十六頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)首先構(gòu)造識(shí)別和字母表中一個(gè)符號(hào)的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換i開(kāi)始識(shí)別正則式的NFAafif開(kāi)始識(shí)別正則式a的NFA3.4從正則式到有限自動(dòng)機(jī)目前三十七頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)構(gòu)造識(shí)別主算符為選擇的正則式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換

fi開(kāi)始識(shí)別正則式s|t的NFAN(s)N(t)3.4從正則式到有限自動(dòng)機(jī)目前三十八頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)構(gòu)造識(shí)別主算符為連接的正則式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換識(shí)別正則式st的NFAiN(s)f開(kāi)始N(t)3.4從正則式到有限自動(dòng)機(jī)目前三十九頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)構(gòu)造識(shí)別主算符為閉包的正則式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換N(s)f開(kāi)始識(shí)別正則式s*的NFAi3.4從正則式到有限自動(dòng)機(jī)目前四十頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)對(duì)于加括號(hào)的正則式(s)，使用N(s)本身作為它的NFA3.4從正則式到有限自動(dòng)機(jī)目前四十一頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)本方法產(chǎn)生的NFA有下列性質(zhì)N(r)的狀態(tài)數(shù)最多是r中符號(hào)和算符總數(shù)的兩倍N(r)只有一個(gè)接受狀態(tài)，接受狀態(tài)沒(méi)有向外的轉(zhuǎn)換3.4從正則式到有限自動(dòng)機(jī)19開(kāi)始0abab6782345目前四十二頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)本方法產(chǎn)生的NFA有下列性質(zhì)N(r)的每個(gè)狀態(tài)有一個(gè)用的符號(hào)標(biāo)記的指向其它結(jié)點(diǎn)的轉(zhuǎn)換，或者最多兩個(gè)指向其它結(jié)點(diǎn)的轉(zhuǎn)換3.4從正則式到有限自動(dòng)機(jī)19開(kāi)始0abab6782345目前四十三頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.4從正則式到有限自動(dòng)機(jī)

19開(kāi)始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解目前四十四頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.4從正則式到有限自動(dòng)機(jī)

19開(kāi)始0ab678ab2345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解目前四十五頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.4從正則式到有限自動(dòng)機(jī)

19開(kāi)始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解目前四十六頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.4從正則式到有限自動(dòng)機(jī)

19開(kāi)始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解目前四十七頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.4從正則式到有限自動(dòng)機(jī)

19開(kāi)始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解目前四十八頁(yè)\總數(shù)五十五頁(yè)\編于十八點(diǎn)3.4從正則式到有限自動(dòng)機(jī)1