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