近日周立功教授公開了數年的心血之作《程序設計與數據結構》，電子版已無償性分享到電子工程師與高校群體下載，經周立功教授授權，特對本書內容進行連載。

>>>>1.1狀態機

>>>1.1.1 有限狀態機

1. 起源

自動機是計算機的簡單理論模型，通常將自動機分為有限自動機和圖靈機。盡管有限自動機更簡單，但在定義圖靈機之后數年，這個概念才被提出來。

沃倫·麥卡洛克當時正在研究腦部創傷治療精神病人，他想研究出一種解釋大腦如何工作的理論。沃爾特·皮茨最初被培養成為一位邏輯學學者，但是卻在全新的數學生物物理學領域發表論文。兩人于1942年相識，認識到他們對相同類型的問題感興趣，于是開始聯手研究彼此取長補短。他們發表了第一篇論文“神經活動中內在的思想邏輯演算”（A Logical Calculus of Ideas Immanent in Nervous Activity），在這篇論文中，他們借助細胞對神經元進行了建模。雖然每個細胞都有多個輸入，但只有一個輸出。一個細胞的輸出必須成為另一個細胞的輸入，輸入的類型有兩種——抑制的和興奮的。如果興奮的輸入超過了一定閾值，且沒有抑制輸入，細胞將會被激活。雖然細胞的集合和它們之間的連接被兩人稱為神經網絡，但他們沒有意識到，這是大腦實際運作的簡化模型，通過研究神經網絡可以得知神經網絡如何處理邏輯活動。他們的網絡模型與神經元和人類的大腦具備相同的特征，因此他們希望自己的研究能夠揭示人類邏輯推理的奧秘。

他們的論文引起了計算機專家約翰·馮·諾依曼和著名的數學家、哲學家諾伯特·維納的注意，兩位學者對這篇論文印象深刻。維納看到了其中蘊含的力量，他意識到，這一觀點具有廣泛的適應性，可以發展出控制論。控制論將催生可以學習的機器的理念，反過來也會孕育人工智能。馮·諾依曼認識到，麥卡洛克和皮茨對細胞和細胞間連接的描述，同樣可以應用到電子組件和計算中。他在《關于EDVAC的報告》（First draft of a report on the EDVAC）一文中對此進行了詳細的描述，正是這篇論文奠定了現代計算機構建的基石。

另一個受到麥卡洛克和皮茨影響的人是馬文·明斯基，1954年明斯基在他的博士論文中對神經網絡進行了研究，展示了如何使用這些網絡對自動機進行全面的描述。明斯基的著作《計算：有限和無限機器》是這一領域的經典之作，高屋建瓴地描述了自動機和計算理論。通過對比物理學，明斯基在這本書的前言中解釋了這種使用理論機器研究的理論為什么能夠發揮作用。

與物理學使用統計定義事件的方法不同，我們是用邏輯定義的計算或表達式。它們被聯系在一起，不是通過幾何或能量性質，而是通過它們與類似機器或類似定義之間的關系。我們能夠使用機器組件進行簡單的交互，應用最顯而易見的邏輯命題。面對等價的現實物理機器時，我們必須解決極端復雜的分析等式。

自動機被劃分為兩類：一類具有有限內存，另一類具有無限內存下面只研究有限的一類。

2.有限狀態機

有限狀態機（Finite State Machine，FSM）是一種抽象的機制， 它包括有限數量的狀態。因此FSM是一個狀態集，值的一個有限集合。

閘機是一個常見的狀態機，這是《敏捷軟件開發——原則、模式與實戰》一書中展示的一個經典示例。在這里，將以香港地鐵站的閘機為例介紹有限狀態機，其用例文本摘要如下：

通常閘機默認是關閉的，當閘機收到有效卡信息時，則打開閘機；當乘客通過后，則關閉閘機。如果有人非法通過，則閘機會發出連續的“滴、滴、滴……”報警聲；如果閘機已經打開，而乘客還在刷卡，則閘機會發出“滴”的聲音提示乘客，并顯示“票價和余額，閘機已經打開，請通過，謝謝！”

FSM會響應“事件”而改變狀態，即將每個“事件”實現為一個函數，當“事件”發生時，就意味著調用了一個函數。FSM也執行動作產生輸出，所執行的動作是當前狀態和輸入事件的一個函數，其目的是執行系統的任務。

事件是指在某個時刻發生的事情，比如，閘機的“刷卡（card）”事件和“通過（pass）”事件，狀態是系統的狀態。事件表示時間點，狀態表示時間段，狀態對應對象接收的兩次事件之間的時間間隔。比如，閘機可能處于的狀態：Locked狀態和Unlocked狀態。

轉換是從一個狀態轉移為另一個狀態的路徑，引發它的事件被稱為事件觸發器，簡稱觸發。而轉換可以觸發動作——表示對象的某個方法的調用，比如，當事件card發生時，閘機從Locked狀態轉換為Unlocked狀態并執行打開閘機動作。轉換還有一個監護條件邏輯測試——或布爾測試，只有測試通過時轉換才發生。

而事件可以是外部事件和內部事件，外部事件是在系統和它的執行者之間傳遞的事件，比如，按下一個鍵和一個來自傳感器的中斷都是外部事件。內部事件是在系統內部的對象之間傳送的事件，比如，溢出異常是一個內部事件。可以用UML對4種事件建模：信號、調用、時間推移或狀態的一次改變。信號或調用可以帶有參數，參數值對轉移（包括監護條件和動作的表達式）是可見的。

信號是一個異步事件，在實例間異步傳遞消息的通信規約。消息是一個具名對象，信號是消息的類型，象類一樣，信號也有屬性和操作。而信號事件是指發送或接收信號的事件，其差別在于信號是對象之間的消息，而信號事件是指在某時某刻發生的事情。

如果事件沒有產生任何效果，則FSM保持狀態不變。通常下一個狀態依賴于當前狀態和輸入事件，有時狀態轉移會導致輸出動作。在某些情況下，雖然一個事件不會立即導致狀態轉換，但它會影響隨后的狀態轉換。如果事件已經產生，則可以將該情況保存為一個條件，在之后進行檢驗。

監護條件是由一個方括號括起來的布爾表達式，放在觸發器事件的后面。其表示法為“事件[條件]”（Event[Condition]），條件是某一段時間內值為True或False。通?！笆录币鹆恕盃顟B轉換”，當事件發生時，為了發生轉換，可選的“條件”的值必須為True，可選的“動作”作為結果被執行。

動作是與狀態轉換相關的可選的輸出，動作執行了計算（調用相應的函數），作為狀態轉換的結果。事件導致狀態轉移，而動作是狀態轉移所產生的效果。動作在狀態轉移時被觸發，執行后自行終止。

● 轉換動作

轉換動作是指從某一狀態轉換為另一狀態時產生的動作，該動作也可能發生在狀態轉換至自身狀態時。為了描述狀態圖中的動作，將狀態轉換表示為：事件/動作（Event/Action）或事件[條件]/動作（Event[Condition]/Action），比如，card/unlock。

考慮閘機狀態圖中的動作：當事件card發生時，閘機從Locked狀態轉換為Unlocked狀態，發生在該狀態轉移中的動作是獲取card信息。作為狀態機的輸出，該動作顯示票價和余額并開鎖。

通常多個動作可以和同一個狀態轉換關聯，因為動作都是并發執行的，所以這些動作之間不能有任何的相互依賴關系。比如，不能同時發生兩個并發的事件——計算余額和顯示余額，因為這兩個動作有先后順序的依賴關系，在余額計算之前不無法顯示出來。為了避開這個問題，可以引入“計算余額”的中間狀態。動作“計算余額”在進入該狀態時執行，動作“顯示余額”在退出該狀態時執行。

● 進入動作

進入動作是指在開始進入該狀態時觸發的即時動作，使用保留字“進入（entry）”表示，在狀態框里表示為“進入/動作（entry/Action），即entry/[action-list]?！?/span>

● 退出動作

退出動作是指在離開該狀態時觸發的即時動作，使用保留字“退出（exit）”表示，在狀態框里表示為“退出/動作（exit/Action），即exit/[action-list]。”

由于狀態圖源自于用例，因此要從用例開發狀態圖。首先需要用例中的一個特定的場景，即從用例中的一條特定路徑描述對象之間的交互，正常的業務序列詳見圖 4.8（a）。

圖 4.8 閘機業務序列圖

如果閘機在Locked狀態收到card事件，則轉移到Unlocked狀態并執行unlock動作，此時閘機將它的狀態改為Unlocked并調用unlock函數；如果閘機在Unlocked狀態收到一個pass事件，則轉移到Locked狀態并執行lock動作，此時閘機將它的狀態改為Locked并調用lock函數。

如圖 4.9 (a)所示為正常的業務序列圖對應狀態圖，由于閘機處于打開狀態或關閉狀態時，“card()”或“pass()”操作對應的處理是不同的，因此難以用一個序列圖清晰地描繪對象交互與狀態的關系。如果以業務實體（閘機）的狀態（打開狀態或關閉狀態）為核心，將執行者與系統交互的具體操作稱之為“事件”，比如，card()、pass()等。

圖 4.9 閘機狀態圖

表4.1 閘機狀態轉移表

這些圖是由狀態、事件、轉換和動作組成的有向圖，圓角矩形表示閘機的狀態，閘機始終保持狀態直到轉換促使它改變狀態。轉換用導向箭頭表示，通常由收到觸發事件的元素發起。當輸入的事件與有向邊上的事件匹配時，閘機將會從一個狀態轉換到另一個狀態。

其中包含了起始狀態、觸發轉移事件、終止狀態和要執行的動作，將其轉換為狀態轉移表的表格，詳見表 4.1。由于狀態轉移表列出了所有狀態下，接收所有事件后的狀態是如何變化的，因此很容易幫助發現遺漏了哪些狀態轉移。雖然狀態轉移表的優點是直觀，但其缺點也是非常明顯的，那就是難以確認狀態轉移的完整性。

顯然，通用狀態圖與狀態表描述狀態機的行為，開發者可以很容易檢查那些未知的，甚至沒有處理的情況。比如，閘機在Unlocked狀態下沒有處理card事件的轉移，且在Locked狀態下也沒有處理pass事件的轉移。假設如果閘機在Locked狀態收到一個非法pass事件，則狀態不變并執行alarm動作，其業務序列圖詳見圖 4.8（b）。如果乘客不熟悉流程，當閘機已經轉移到Unlocked狀態時，而乘客還在刷卡（card），則閘機會發出“滴”的聲音提示乘客，并顯示“票價和余額，閘機已經打開，請通過，謝謝！” 其業務序列圖詳見圖 4.8（c），完整的閘機狀態轉移表詳見表 4.2。

表4.2 完整的閘機狀態轉移表

在關閉狀態下，當需要增加報警功能時，只需要新增一條事件/動作線，詳見圖 4.9(b)。同理，增加一條事件/動作線表示閘門在已經打開時繼續刷卡的情況，詳見圖 4.9(c)。由于這兩種情況不會改變閘機的狀態，因此導向箭頭起始和結束均為同一狀態。