系統(tǒng)程序員成長(zhǎng)計(jì)劃-文本處理(一)
狀態(tài)機(jī)(1)
o 有窮狀態(tài)機(jī)的形式定義
有窮狀態(tài)機(jī)是一個(gè)五元組 (Q，Σ，δ，q0，F(xiàn))，其中：
Q是一個(gè)有窮集合，稱為狀態(tài)集。
Σ是一個(gè)有窮集合，稱為字母表。
δ: Q xΣ?Q稱為狀態(tài)轉(zhuǎn)移函數(shù)。
q0 是初始狀態(tài)。
F 是接受狀態(tài)集。
教科書上是這樣定義有窮自動(dòng)機(jī)的，這個(gè)形式定義精確的描述了有窮狀態(tài)機(jī)的含義。但是大部分人(包括我自己)第一次看到它時(shí)，反復(fù)的讀上幾遍，仍然不知道它在說(shuō)什么。幸好通過(guò)一些實(shí)例，我們可以很容易明白有窮狀態(tài)機(jī)的原理。
自動(dòng)門是一個(gè)典型的有窮狀態(tài)機(jī)：
它有“開(kāi)”和“關(guān)”兩種狀態(tài)，這就是它的狀態(tài)集，也就是上面所說(shuō)的Q。
人可以從自動(dòng)門進(jìn)來(lái)或出去，當(dāng)人進(jìn)來(lái)或出去的時(shí)候，自動(dòng)門會(huì)自動(dòng)打開(kāi)，如果在規(guī)定的時(shí)間內(nèi)沒(méi)有人進(jìn)出，自動(dòng)門會(huì)自動(dòng)關(guān)上。人的進(jìn)來(lái)、出去和超時(shí)三個(gè)事件是自動(dòng)門的字母表，也就是上面所說(shuō)的Σ。而自動(dòng)門在當(dāng)前狀態(tài)下，對(duì)事件的響應(yīng)，會(huì)引起狀態(tài)的變化，這就是狀態(tài)轉(zhuǎn)換函數(shù)，也就是上面所說(shuō)的δ。
自動(dòng)門剛安裝好的時(shí)候，我們可以認(rèn)為它是關(guān)上的，所以關(guān)閉狀態(tài)是自動(dòng)門的初始狀態(tài)。
在理想情況下，自動(dòng)門會(huì)一直運(yùn)行，所以它沒(méi)有接受狀態(tài)，接受狀態(tài)集F是空集。
有窮狀態(tài)機(jī)的形式定義很精確，文字描述比較通俗，而圖形表示則比較直觀。通用建模語(yǔ)言（UML）里的狀態(tài)圖是狀態(tài)機(jī)的常用圖形表示方法。簡(jiǎn)單的狀態(tài)圖包括一些狀態(tài)，用圓角方框表示，里面有狀態(tài)的名稱。狀態(tài)之間的轉(zhuǎn)換，用箭頭表示，上面可以加轉(zhuǎn)換條件。自動(dòng)門的狀態(tài)機(jī)可以用下圖表示：
有窮狀態(tài)機(jī)很簡(jiǎn)單，在生活中可以找出很多這樣的例子。但是教科書里講得太復(fù)雜了，一會(huì)兒證明確定性有窮狀態(tài)機(jī)和非確定性有窮狀態(tài)機(jī)的等價(jià)性，一會(huì)兒證明正則表達(dá)式的正則運(yùn)算是封閉的，一會(huì)兒又來(lái)個(gè)泵引理。花了很長(zhǎng)時(shí)間，我才明白這些原理，但兩年之后，我又把它們忘得一干二凈。
主要原因是工作中沒(méi)有機(jī)會(huì)運(yùn)用它們，這些理論的證明于編程沒(méi)有太大用處，不過(guò)狀態(tài)機(jī)本身卻是文本處理利器，由于程序員在很多場(chǎng)合下都是在與文本數(shù)據(jù)打交道，所以狀態(tài)機(jī)是程序員必備的工具之一。這里我們將一起學(xué)習(xí)如何用狀態(tài)機(jī)來(lái)處理文本數(shù)據(jù)，后面我們也會(huì)提到狀態(tài)機(jī)的其它用途，不過(guò)不是本節(jié)的重點(diǎn)。
文章出處：http://www.limodev.cn/blog
作者聯(lián)系方式：李先靜 <xianjimli at hotmail dot com>