從正規(guī)式開始

一、先將正規(guī)式轉(zhuǎn)換成NFA

通過下面的對(duì)應(yīng)法則將正規(guī)式轉(zhuǎn)換成NFA

例如：

二、再將NFA轉(zhuǎn)成DFA（子集法）

運(yùn)用子集法的3個(gè)概念：
(1 )狀態(tài)集的ε-閉包: 狀態(tài)集I中的任何狀態(tài)s經(jīng)任意條ε弧而能到達(dá)的所有狀態(tài)的集合，定義為狀態(tài)集I的ε -閉包，表示為ε -closure()。

(2)狀態(tài)集的a弧轉(zhuǎn)換: 狀態(tài)集I中的任何狀態(tài)s經(jīng)過一條a弧而能到達(dá)的所有狀態(tài)的集合，定義為狀態(tài)集1的a弧轉(zhuǎn)換，表示為move(l,a)。

(3)狀態(tài)集的a弧轉(zhuǎn)換的閉包a: lg= ε-closure(move(l,a))

上面的正規(guī)式轉(zhuǎn)換成NFA：

先從初態(tài)0開始求：
??【因?yàn)槊總€(gè)狀態(tài)通過一條ε弧到達(dá)自己本身，所以求得ε的閉包包含自己】
（1）求0的ε的閉包：經(jīng)過任意條ε所能到達(dá)的狀態(tài)，集合為{0,1,3,4,5,6,7,9}
（2）求0的a弧轉(zhuǎn)換：1經(jīng)過a弧到達(dá)2，4經(jīng)過a弧到達(dá)4，其余沒有經(jīng)過一條a弧到達(dá)某個(gè)狀態(tài)，所以集合為{2,4}
（3）求a弧轉(zhuǎn)換的閉包：{2,4}分別經(jīng)過任意條ε所能到達(dá)的狀態(tài)，集合為{2,4,6,7,9}
（4）求0的b弧轉(zhuǎn)換：5經(jīng)過b到5，7經(jīng)過b到8，，其余沒有經(jīng)過一條b弧到達(dá)某個(gè)狀態(tài)，所以集合為{5,8}
（5）求b弧轉(zhuǎn)換的閉包：{5,8}分別經(jīng)過任意條ε所能到達(dá)的狀態(tài)，集合為{5,6,7,8,9}
0的ε-閉包：{0,1,3,4,5,6,7,9}
0的a弧轉(zhuǎn)換：{2,4}
0的a弧轉(zhuǎn)換的ε-閉包：{2,4,6,7,9}
0的b弧轉(zhuǎn)換：{5,8}
0的b弧轉(zhuǎn)換的ε-閉包：{5,6,7,8,9}
現(xiàn)在列一個(gè)表格：
（1）表格的列數(shù)為輸入字符的個(gè)數(shù)+1，此題為a，b兩個(gè)輸入字符，所以為3列。
（2）第一列第一行填寫初態(tài)的ε-閉包（此題0的ε-閉包），第二列第一行填寫初態(tài)的a弧轉(zhuǎn)換的ε-閉包（此題0的a弧轉(zhuǎn)換的ε-閉包），第三列第一行填寫初態(tài)的b弧轉(zhuǎn)換的ε-閉包（此題0的b弧轉(zhuǎn)換的ε-閉包）......以此類推。
（3）第一列的第二行以下填入上一行第二列以后的沒有出現(xiàn)過的狀態(tài)集。（此題第一行第二列第三列都沒有出現(xiàn)在第一列中，將他們填入第一列）

下圖為填好的表：
【新的終態(tài)的判斷方法就是包含原來終態(tài)的集合就為終態(tài)，例如此題原來終態(tài)為9，所以包含9的集合就為終態(tài)，[雙圈代表終態(tài)]；
新的初態(tài)就是包含原來初態(tài)的集合就為初態(tài)，例如此題原來初態(tài)為0，所以包含0的集合就為初態(tài)】

為表里的狀態(tài)集重新標(biāo)上號(hào)：

三、將DFA最小化

先了解幾個(gè)概念：
1.多于狀態(tài)：對(duì)于一個(gè)狀態(tài)Si，若從開始狀態(tài)出發(fā)，不可能到達(dá)改狀態(tài)Si，則Si為多余（無用）狀態(tài)。
2.死狀態(tài)：對(duì)于一個(gè)狀態(tài)Si，對(duì)于任意輸入符號(hào)a，若轉(zhuǎn)到它本身后，不可能從它到達(dá)終止?fàn)顟B(tài)，則稱Si為死狀態(tài)。
都稱為無關(guān)狀態(tài)
3.等價(jià)狀態(tài)：若Si為自動(dòng)機(jī)的一個(gè)狀態(tài)，我們把從Si出發(fā)能導(dǎo)出的所有符號(hào)串的集合記為L(zhǎng)（Si）。
設(shè)有兩個(gè)狀態(tài)Si和Sj，若有L（Si）=L（Sj），則稱Si和Sj是等價(jià)狀態(tài)。
4.可區(qū)別狀態(tài)：自動(dòng)機(jī)中兩個(gè)狀態(tài)Si和Sj，如果它們不等價(jià)，則稱它們可區(qū)別。
5.兩個(gè)狀態(tài)(Si和Sj)等價(jià)的判斷條件:
（1）狀態(tài)Si和Sj必須同時(shí)為終止?fàn)顟B(tài)或同時(shí)為非終止?fàn)顟B(tài)。即終止?fàn)顟B(tài)和非終止?fàn)顟B(tài)是可區(qū)別的。
（2）狀態(tài)Si和Sj對(duì)于任意輸入符a∈Σ，必須轉(zhuǎn)到等價(jià)的狀態(tài)里，否則Si和Sj是可區(qū)別的。

DFA的化簡(jiǎn)算法：對(duì)于DFA M=(S,Σ,f,S0,Z)
(1)首先將DFA的狀態(tài)集進(jìn)行初始化，分成Π=(Z,S-Z);
(2) 用下面的過程對(duì)Π構(gòu)造新的劃分Π new
for (Π中每個(gè)組G) do //每個(gè)組都是一個(gè)狀態(tài)集
begin
把G劃分成小組，G中的任意兩個(gè)狀態(tài)Si和Sj在同一組中，當(dāng)且僅當(dāng)對(duì)于Σ中任意輸入符號(hào)a ，Si和Sj的a轉(zhuǎn)換是到同一組中，move(Si,a) ∈Gi ，move(Sj,a) ∈Gi。這樣，只要Si和Sj的a轉(zhuǎn)換是到不同的組中，則說明Si和Sj是可區(qū)別的，可進(jìn)行劃分。在Π new中用剛完成的對(duì)G的劃分代替原來的G。
end ; Π := Π new；
(3)重復(fù)執(zhí)行(2)，直到Π中每個(gè)狀態(tài)集不能再劃分(Π new= Π)為止;
(4)合并等價(jià)狀態(tài) ,在每個(gè)G中，取任意狀態(tài)作為代表，刪去其它狀態(tài);
(5)刪去無關(guān)狀態(tài)，從其它狀態(tài)到無關(guān)狀態(tài)的轉(zhuǎn)換都成為無定義。
舉例：

image.png

之前上面這個(gè)圖畫錯(cuò)了,現(xiàn)在圖已經(jīng)修改過了,謝謝提醒 :-D