學(xué)習(xí)編譯原理Time09 ~ 正則表達式轉(zhuǎn)化為有窮自動機

在說從正則表達式到有窮自動機之前，想提一下不確定的有窮自動機，因為正則表達式轉(zhuǎn)化為確定的有窮自動機(DFA)是比較困難，而正則表達式轉(zhuǎn)化為不確定的有窮自動機(NFA)是比較好實現(xiàn)的，本文就記錄這個，下一篇筆記再談?wù)凬FA轉(zhuǎn)化為DFA。

首先簡單說一下，不確定的有窮自動機(NFA)

M=(S ,  ∑ , δ , s0, F )

S：有窮狀態(tài)集

∑：輸入字母表，即輸入符號集合。假設(shè) ε 不是∑中的元素

δ：將S X ∑映射到2^S的轉(zhuǎn)換函數(shù)。 s ∈S ，a∈∑，δ(s,a)表示從狀態(tài)s出發(fā)，沿著標號為a的邊所能到達的狀態(tài)集合（與DFA唯一區(qū)別的點）

s0：開始狀態(tài)(或初始狀態(tài))，s0∈S

F：接收狀態(tài)(或終止狀態(tài))集合，F(xiàn)S

示例一個不確定的有窮自動機如下：

根據(jù)轉(zhuǎn)換圖可以看出，狀態(tài)0遇到符號a的時候，就進入狀態(tài)集合中，集合包含狀態(tài)1和狀態(tài)0；狀態(tài)0遇到符號b的時候，就進入狀態(tài)集合中，只包含狀態(tài)0，同理，狀態(tài)1遇到符號b的時候，就進入狀態(tài)集合中，只包含狀態(tài)2，...

接下來的就是根據(jù)正則表達式構(gòu)造NFA

直接舉一個例子：

r=(a | b)*abb

第一步：首先確定初始狀態(tài)和終止狀態(tài)，然后將有向邊上的表達式進行分解

第二步：然后確定后綴部分abb，已經(jīng)不能分解了

第三步：分解（a|b）*，因為帶*是克林閉包

第四步：再分解，最終轉(zhuǎn)化成NFA

    

記錄

點點滴滴的筆記

歡迎關(guān)注，共同學(xué)習(xí)

小浩筆記