學(xué)習(xí)編譯原理Time08 ~ 確定的有窮自動機(jī)及算法實現(xiàn)
有窮自動機(jī)(FA)分為確定的有窮自動機(jī)(DFA)和不確定的有窮自動機(jī)(NFA).
本筆記主要記錄的是確定的有窮自動機(jī)(DFA)
M=(S , ∑ , δ , s0, F )
S：有窮狀態(tài)集
∑：輸入字母表，即輸入符號集合。假設(shè) ε 不是∑中的元素
δ：將S X ∑映射到S的轉(zhuǎn)換函數(shù)。 
s ∈S ，a∈∑，δ(s,a)表示從狀態(tài)s出發(fā)，沿著標(biāo)號為a的邊所能到達(dá)的狀態(tài)
s0：開始狀態(tài)(或初始狀態(tài))，s0∈S
F：接收狀態(tài)(或終止?fàn)顟B(tài))集合，F(xiàn)
S
示例一個確定的有窮自動機(jī)如下：
根據(jù)轉(zhuǎn)換圖可以看出，狀態(tài)0遇到符號a的時候，就進(jìn)入狀態(tài)1，或狀態(tài)0遇到符號b的時候，依然還是狀態(tài)0，同樣的道理，狀態(tài)1遇到符號a的時候，還保持狀態(tài)1，遇到符號b的時候就進(jìn)入狀態(tài)2；狀態(tài)2遇到符號1的時候回到狀態(tài)1，遇到符號b的時候進(jìn)入狀態(tài)3；狀態(tài)3有個圓點表示終態(tài)，狀態(tài)遇到符號a就進(jìn)入狀態(tài)1，遇到符號符號b就回到狀態(tài)0。轉(zhuǎn)換表也可以表示確定的有窮自動機(jī)。
接下來談?wù)凞FA的算法實現(xiàn)
輸入：以文件結(jié)束符eof結(jié)尾的字符串x。DFA的開始狀態(tài)s0，接收狀態(tài)集F，轉(zhuǎn)換函數(shù)move。
輸出：如果DFA成功接收字符串x，則回答“yes”，否則回答“no”。
方法：將下述算法應(yīng)用于輸入串x。
s=s0;
c=nextChar();
while(c!=eof)
{
s=move(s,c);
c=nextChar();
}
if(s 在 F 中)
return "yes";
else
return "no";函數(shù)nextChar()返回輸入串x的下一個符號
函數(shù)move(s, c)表示從狀態(tài)s出發(fā)，沿著標(biāo)記為c的邊所能到達(dá)的狀態(tài)
小浩筆記
