計算機的簡單理論模型到有限狀態(tài)機

近日周立功教授公開了數(shù)年的心血之作《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》，電子版已無償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對本書內(nèi)容進行連載。

>>>>1.1狀態(tài)機

>>>1.1.1 有限狀態(tài)機

1. 起源

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

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

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

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

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

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

2.有限狀態(tài)機

有限狀態(tài)機（Finite State Machine，F(xiàn)SM）是一種抽象的機制， 它包括有限數(shù)量的狀態(tài)。因此FSM是一個狀態(tài)集，值的一個有限集合。

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

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

FSM會響應(yīng)“事件”而改變狀態(tài)，即將每個“事件”實現(xiàn)為一個函數(shù)，當(dāng)“事件”發(fā)生時，就意味著調(diào)用了一個函數(shù)。FSM也執(zhí)行動作產(chǎn)生輸出，所執(zhí)行的動作是當(dāng)前狀態(tài)和輸入事件的一個函數(shù)，其目的是執(zhí)行系統(tǒng)的任務(wù)。

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

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

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

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

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

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

動作是與狀態(tài)轉(zhuǎn)換相關(guān)的可選的輸出，動作執(zhí)行了計算（調(diào)用相應(yīng)的函數(shù)），作為狀態(tài)轉(zhuǎn)換的結(jié)果。事件導(dǎo)致狀態(tài)轉(zhuǎn)移，而動作是狀態(tài)轉(zhuǎn)移所產(chǎn)生的效果。動作在狀態(tài)轉(zhuǎn)移時被觸發(fā)，執(zhí)行后自行終止。

● 轉(zhuǎn)換動作

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

考慮閘機狀態(tài)圖中的動作：當(dāng)事件card發(fā)生時，閘機從Locked狀態(tài)轉(zhuǎn)換為Unlocked狀態(tài)，發(fā)生在該狀態(tài)轉(zhuǎn)移中的動作是獲取card信息。作為狀態(tài)機的輸出，該動作顯示票價和余額并開鎖。

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

● 進入動作

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

● 退出動作

退出動作是指在離開該狀態(tài)時觸發(fā)的即時動作，使用保留字“退出（exit）”表示，在狀態(tài)框里表示為“退出/動作（exit/Action），即exit/[action-list]?！?/span>

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

圖 4.8 閘機業(yè)務(wù)序列圖

如果閘機在Locked狀態(tài)收到card事件，則轉(zhuǎn)移到Unlocked狀態(tài)并執(zhí)行unlock動作，此時閘機將它的狀態(tài)改為Unlocked并調(diào)用unlock函數(shù)；如果閘機在Unlocked狀態(tài)收到一個pass事件，則轉(zhuǎn)移到Locked狀態(tài)并執(zhí)行l(wèi)ock動作，此時閘機將它的狀態(tài)改為Locked并調(diào)用lock函數(shù)。

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

圖 4.9 閘機狀態(tài)圖

表4.1 閘機狀態(tài)轉(zhuǎn)移表

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

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

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

表4.2 完整的閘機狀態(tài)轉(zhuǎn)移表

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