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