最近得做一些跟自動機(jī)有關(guān)的東東，其中一部分可以簡要地看作是由一套正則文法生成狀態(tài)自動機(jī)的過程。

什么是正則表達(dá)式？

首先我們看看什么是正則表達(dá)式。這個東東呢，一般用于描述一個字符串的集合——直接說就是一個正則表達(dá)式可能可以匹配一大堆字符串，而這一大堆字符串可以形成一個集合，它們的共同特征就是可以被這個正則表達(dá)式匹配。就像去死去死團(tuán)，但是不同的是去死去死團(tuán)的團(tuán)員的共同特征是不被任何異性所匹配——但是這沒關(guān)系，我們不妨取去死去死團(tuán)的補集就行了。

反正正則表達(dá)是很好啦，因為你只要用一點點在臟話里，就可以罵好多好多人，比如：

Mar(y|k|cus) is son of bitch.

真是非常de省力，唯一的缺點是可能對方不知道你在說什么。

好了，從上面我們可以看出正則表達(dá)式中的兩個基本結(jié)構(gòu)：

·                                 連結(jié) (Concatenation)，比如 bitch，由b, i, t, c, h連接而成

·                                 聯(lián)合 (Union)，比如 y|k|cus，可以認(rèn)為是y或k或者cus

下面是第三個基本結(jié)構(gòu)，被稱為Kleene star (或者 Kleene 閉包)的。因為這個操作是Stephen Cole Kleene發(fā)明的。啊啊，其實正則表達(dá)式這個東西就是Kleene發(fā)明的。這個同學(xué)真是非常的牛B，因為他是更加牛B的 阿隆佐 - 丘奇 ( Alonzo Church )——歷史上和阿蘭 - 圖靈 ( Alan Turing ) 并稱的人物——的學(xué)生。有多牛B呢，這個Kleene還和他的老師，還有圖靈，就遞歸論發(fā)表了論文，奠定了可計算理論的根基。啊哈哈哈，真是牛B啊。

嗯，所謂Kleene Star的例子就是這樣的。

·                                 Kleene Star，比如a*，可以接受空串和若干個a連結(jié)組成的串

當(dāng)然咯，還有一些別的操作，比如我們知道的+，?，集合[]等等，但是這些操作都可以通過上面三個基本操作的組合來完成。

比如+，a+可以認(rèn)為是aa*

什么是NFA？

要說NFA嘛，我得先說說DFA。所謂DFA，就是Deterministic Finite state Automata的簡稱。是狀態(tài)機(jī)的一種。通俗的說，就是一大堆狀態(tài)的集合，里面有一個初始狀態(tài)和若干終止?fàn)顟B(tài)，每個狀態(tài)可以有若干個輸出邊前往別的狀態(tài)。但是要求每個狀態(tài)的同一種輸出邊至多只有一個，所以自動機(jī)被稱為是”Deterministic”的。

比如下面這個例子：

表述的是一個電燈de開關(guān)，這個開關(guān)每按一下就從’開’狀態(tài)轉(zhuǎn)換到’關(guān)’狀態(tài)，或者從’關(guān)’狀態(tài)轉(zhuǎn)換到’開’狀態(tài)。而為了從環(huán)保角度出發(fā)，在’關(guān)’狀態(tài)才被認(rèn)為是終止態(tài)。

上面的自動機(jī)呢，就可以描述這個燈泡的行為模式，或者說可以描述電燈的狀態(tài)轉(zhuǎn)換過程。輸出邊就是’開’或者’關(guān)’的動作，或者說這個燈泡的開關(guān)，只接受這兩種動作：“Trun On”，“Trun Off”。而”Trun On”動作只會導(dǎo)致燈的狀態(tài)變成“On”，“Trun Off”動作只會導(dǎo)致燈的狀態(tài)變成“Off”，這是確定的，你的外婆都可以預(yù)料到的。所以說DFA是確定有限狀態(tài)自動機(jī)。

現(xiàn)在可以說NFA了。這個NFA嘛，全稱是Non-deterministic Finite state Automata。也是狀態(tài)自動機(jī)的一種。確切地說，剛才的DFA是NFA的一個子集。和DFA唯一的區(qū)別就是他是”Non-deterministic”的，哈，非確定的，每個狀態(tài)的同一種輸出邊可以不止一個。

還是用剛才的例子。現(xiàn)在假設(shè)我們的電燈有一種新的狀態(tài)咯～：壞掉了。燈絲被過大的電流燒斷了，聽上去遭透了，因為一”Trun On”就得準(zhǔn)備換燈泡了：

但是我們沒法確定的知道哪一次Trun On會導(dǎo)致燈泡壞掉，使得燈泡進(jìn)入”Down”狀態(tài)的那次“開”操作看上去跟你昨天開燈的那次操作一模一樣（嚴(yán)格的說，每一次點亮燈泡都會導(dǎo)致燈絲的狀態(tài)發(fā)生變化，但是在此簡化了）

所以從狀態(tài)”O(jiān)ff”出來的輸出邊中，”Trun On”有兩條，這就導(dǎo)致沒法根據(jù)當(dāng)前狀態(tài)和輸出邊確定下一狀態(tài)，這就是為什么稱為非確定性有限自動機(jī)的原因。

如何轉(zhuǎn)換？

剛才Shellex說了，正則表達(dá)式有三種基本結(jié)構(gòu)。如果能先將這三種基本結(jié)構(gòu)轉(zhuǎn)換成對應(yīng)的NFA，然后在用這三種基本結(jié)構(gòu)去拼裝成完整的NFA是不是很省力呢？

下面就是三種基本正則表達(dá)式的NFA

ab:

a*:

a|b:

里面出現(xiàn)了一種叫“None”的邊。這個不代表這個邊是字面上的“None”，而是指這個邊是個空邊。也就是說任何“動作”都可以從這個邊進(jìn)入下一個狀態(tài)。它的學(xué)名叫 epsilon 邊，一般表示成’ε’，Shellex這里表示成“None”了。

下面我們來考慮正則表達(dá)式到NFA轉(zhuǎn)換。給出一個正則串的輸入，得到一個NFA的輸出。被廣泛采用的是Thompson Algorithm，也就是所謂的子集算法。該算法的發(fā)明人應(yīng)該就是寫ed編輯器的那個Thompson大牛。該算法的實現(xiàn)和算術(shù)表達(dá)式的求值非常的類似，需要一個符號棧存放操作符，一個自動機(jī)棧存放生成的自動機(jī)。算法結(jié)束后，可以從自動機(jī)棧中Pop一個最終的結(jié)果。

比如對于正則表達(dá)式(a|b)*cd，求值過程如下：

PUSH a To automaton stack

PUSH b To automaton stack

UNION

STAR

PUSH c To automaton stack

CONCAT

PUSH d To automaton stack

CONCAT

POP result

里面的UNION，STAR 和 CONCAT就是三種基本結(jié)構(gòu)的生成操作了。而這三種基本操作的實現(xiàn)是這樣的：

Star：

POP T from automaton stack

CREATE state A, B

ADD transition from A to B with 'ε'

ADD transition from A to T.entry with 'ε'

ADD transition from T.exit to A with 'ε'

ADD transition from T.exit to B with 'ε'

ADD state A, B to T

PUSH T to automaton stack

Concat：

POP F, S from automaton stack

ADD transition from F.exit to S.entry with 'ε'

JOIN S to F

SET F.exit = S.exit

SET F.inputSet += S.inputSet

PUSH F to automaton stack

Union:

POP F, S from automaton stack

CREATE state A, B

ADD transition from A to F.entry with 'ε'

ADD transition from A to S.entry with 'ε'

ADD transition from T.exit to B with 'ε'

ADD transition from T.exit to B with 'ε'

JOIN S to F

ADD state A, B to T

SET F.exit = S.exit

SET F.inputSet += S.inputSet

PUSH F to automaton stack