有限狀態(tài)機(jī)課件

1、關(guān)于有限狀態(tài)機(jī)第一張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月1. 有限狀態(tài)機(jī)的基本概念2. 有限狀態(tài)機(jī)編程方法主要內(nèi)容第二張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20222通信軟件設(shè)計(jì)狀態(tài)機(jī)的引入狀態(tài)機(jī)理論最初的發(fā)展在數(shù)字電路設(shè)計(jì)領(lǐng)域。在數(shù)字電路方面，根據(jù)輸出是否與輸入信號(hào)有關(guān)，狀態(tài)機(jī)可以劃分為Mealy型和Moore型狀態(tài)機(jī)。 Moore型狀態(tài)機(jī)的輸出只和當(dāng)前狀態(tài)有關(guān)，和輸入無(wú)關(guān)。 Mealy型狀態(tài)機(jī)的輸入是由當(dāng)前狀態(tài)和輸入共同決定。而在軟件設(shè)計(jì)領(lǐng)域，狀態(tài)機(jī)的理論儼然已經(jīng)自成一體，它經(jīng)常用來(lái)描述一些復(fù)雜的算法，表明一些算法的內(nèi)部的結(jié)構(gòu)和流程，更多的關(guān)注于程序?qū)ο蟮膱?zhí)行順序。第三

2、張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20223通信軟件設(shè)計(jì)靜態(tài)順序結(jié)構(gòu)動(dòng)態(tài)結(jié)構(gòu)第四張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20224通信軟件設(shè)計(jì)有限狀態(tài)機(jī)有限自動(dòng)機(jī)（Finite Automata Machine）是計(jì)算機(jī)科學(xué)的重要基石，它在軟件開(kāi)發(fā)領(lǐng)域內(nèi)通常被稱(chēng)作有限狀態(tài)機(jī)（Finite State Machine），是一種應(yīng)用非常廣泛的軟件設(shè)計(jì)模式。有限狀態(tài)機(jī)的作用主要是描述對(duì)象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，以及如何響應(yīng)來(lái)自外界的各種事件。在現(xiàn)實(shí)中，有許多事情可以用有限個(gè)狀態(tài)來(lái)表達(dá)，如: 紅綠燈、電話機(jī)等等。 其實(shí)，在資訊領(lǐng)域中，很多事情都是由有限的狀態(tài)

3、所組成，再由于不同的輸入而衍生出各個(gè)狀態(tài)。 第五張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20225通信軟件設(shè)計(jì)有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSM思想廣泛應(yīng)用于硬件控制電路設(shè)計(jì)，也是軟件上常用的一種處理方法(軟件上稱(chēng)為FMM-有限消息機(jī))。它把復(fù)雜的控制邏輯分解成有限個(gè)穩(wěn)定狀態(tài)，在每個(gè)狀態(tài)上判斷事件，變連續(xù)處理為離散數(shù)字處理，符合計(jì)算機(jī)的工作特點(diǎn)。同時(shí)，因?yàn)橛邢逘顟B(tài)機(jī)具有有限個(gè)狀態(tài)，所以可以在實(shí)際的工程上實(shí)現(xiàn)。但這并不意味著其只能進(jìn)行有限次的處理，相反，有限狀態(tài)機(jī)是閉環(huán)系統(tǒng)，有限無(wú)窮，可以用有限的狀態(tài)，處理無(wú)窮的事務(wù)。第六張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20226通信

4、軟件設(shè)計(jì)有限狀態(tài)機(jī)例1紅綠燈 紅綠燈運(yùn)作的原理相當(dāng)簡(jiǎn)單，從一開(kāi)始綠燈，經(jīng)過(guò)一段時(shí)間后，將變?yōu)辄S燈， 再隔一會(huì)兒，就會(huì)變成紅燈，如此不斷反覆。 其FSM如下。 第七張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20227通信軟件設(shè)計(jì)有限狀態(tài)機(jī)例2自動(dòng)販?zhǔn)蹤C(jī) 假設(shè)有簡(jiǎn)單的一自動(dòng)販賣(mài)機(jī)販?zhǔn)蹆深?lèi)商品，一類(lèi)售價(jià)20元，另一類(lèi)售價(jià)50元。 如果該販賣(mài)機(jī)只能辨識(shí)10元及50元硬幣。 一開(kāi)始機(jī)器處于Hello的狀態(tài)，當(dāng)投入10元時(shí)，機(jī)器會(huì)進(jìn)入余額不足的狀態(tài)，直到投入的金額大于20元為止。 如果一次投入50元，則可以選擇所有的產(chǎn)品，否則就只能選擇20元的產(chǎn)品。 完成選擇后，將會(huì)賣(mài)出商品并且找回剩余的零錢(qián)

5、，隨后，機(jī)器又將返回初始的狀態(tài)。 其FSM如下。 第八張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20228通信軟件設(shè)計(jì)基本概念在描述有限狀態(tài)機(jī)時(shí)，常會(huì)碰到的幾個(gè)基本概念：狀態(tài)（State）指的是對(duì)象在其生命周期中的一種狀況，處于某個(gè)特定狀態(tài)中的對(duì)象必然會(huì)滿足某些條件、執(zhí)行某些動(dòng)作或者是等待某些事件。 事件（Event）指的是在時(shí)間和空間上占有一定位置，并且對(duì)狀態(tài)機(jī)來(lái)講是有意義的那些事情。事件通常會(huì)引起狀態(tài)的變遷，促使?fàn)顟B(tài)機(jī)從一種狀態(tài)切換到另一種狀態(tài)。 轉(zhuǎn)換（Transition）指的是兩個(gè)狀態(tài)之間的一種關(guān)系，表明對(duì)象將在第一個(gè)狀態(tài)中執(zhí)行一定的動(dòng)作，并將在某個(gè)事件發(fā)生同時(shí)某個(gè)特定條件

6、滿足時(shí)進(jìn)入第二個(gè)狀態(tài)。 動(dòng)作（Action）指的是狀態(tài)機(jī)中可以執(zhí)行的那些原子操作，所謂原子操作指的是它們?cè)谶\(yùn)行的過(guò)程中不能被其他消息所中斷，必須一直執(zhí)行下去。 第九張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.20229通信軟件設(shè)計(jì)有限狀態(tài)機(jī)模型通信協(xié)議建?；境霭l(fā)點(diǎn)：認(rèn)為通信協(xié)議主要是由響應(yīng)多個(gè)“事件”的相對(duì)簡(jiǎn)單的處理過(guò)程組成。狀態(tài)轉(zhuǎn)移圖優(yōu)點(diǎn)：簡(jiǎn)單明了，比較精確。缺點(diǎn)：對(duì)許多復(fù)雜的協(xié)議，事件數(shù)和狀態(tài)數(shù)會(huì)劇增，處理困難。第十張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202210通信軟件設(shè)計(jì)為什么使用有限狀態(tài)機(jī)在面向?qū)ο蟮能浖到y(tǒng)中，一個(gè)對(duì)象無(wú)論多么簡(jiǎn)單或者多么復(fù)雜，都必然會(huì)

7、經(jīng)歷一個(gè)從開(kāi)始創(chuàng)建到最終消亡的完整過(guò)程，這通常被稱(chēng)為對(duì)象的生命周期。對(duì)象在其生命期內(nèi)是不可能完全孤立的，它必須通過(guò)發(fā)送消息來(lái)影響其它對(duì)象，或者通過(guò)接受消息來(lái)改變自身。第十一張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202211通信軟件設(shè)計(jì)為什么使用有限狀態(tài)機(jī)在銀行客戶(hù)管理系統(tǒng)中，客戶(hù)類(lèi)（Customer）的實(shí)例在需要的時(shí)候，可能會(huì)調(diào)用帳戶(hù)（Account）類(lèi)中定義的getBalance()方法。在這種簡(jiǎn)單的情況下，類(lèi)Customer并不需要一個(gè)有限狀態(tài)機(jī)來(lái)描述自己的行為，主要原因在于它當(dāng)前的行為并不依賴(lài)于過(guò)去的某個(gè)狀態(tài)。并不是所有情況都會(huì)如此簡(jiǎn)單，事實(shí)上許多實(shí)用的軟件系統(tǒng)都必須維護(hù)

8、一兩個(gè)非常關(guān)鍵的對(duì)象，它們通常具有非常復(fù)雜的狀態(tài)轉(zhuǎn)換關(guān)系，而且需要對(duì)來(lái)自外部的各種事件進(jìn)行響應(yīng)。例如，在VoIP電話系統(tǒng)（找狀態(tài)圖）中，電話類(lèi)（Telephone）的實(shí)例必須能夠響應(yīng)來(lái)自對(duì)方的隨機(jī)呼叫，來(lái)自用戶(hù)的按鍵事件，以及來(lái)自網(wǎng)絡(luò)的信令等。在處理這些消息時(shí)，類(lèi)Telephone所要采取的行為完全依賴(lài)于它當(dāng)前所處的狀態(tài)，此時(shí)使用狀態(tài)機(jī)將是一個(gè)不錯(cuò)的選擇。第十二張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202212通信軟件設(shè)計(jì)為什么使用有限狀態(tài)機(jī)游戲引擎是有限狀態(tài)機(jī)最為成功的應(yīng)用領(lǐng)域之一，由于設(shè)計(jì)良好的狀態(tài)機(jī)能夠被用來(lái)取代部分的人工智能算法，因此游戲中的每個(gè)角色或者器件都有可能內(nèi)嵌

9、一個(gè)狀態(tài)機(jī)。考慮RPG（ Role-playing Game）游戲中城門(mén)這樣一個(gè)簡(jiǎn)單的對(duì)象，它具有打開(kāi)（Opened）、關(guān)閉（Closed）、上鎖（Locked）、解鎖（Unlocked）四種狀態(tài)。當(dāng)玩家到達(dá)一個(gè)處于狀態(tài)Locked的門(mén)時(shí)，如果此時(shí)他已經(jīng)找到了用來(lái)開(kāi)門(mén)的鑰匙，那么他就可以利用它將門(mén)的當(dāng)前狀態(tài)轉(zhuǎn)變?yōu)閁nlocked，進(jìn)一步還可以通過(guò)旋轉(zhuǎn)門(mén)上的把手將其狀態(tài)轉(zhuǎn)變?yōu)镺pened，從而成功進(jìn)入城內(nèi)。第十三張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202213通信軟件設(shè)計(jì)控制城門(mén)的狀態(tài)機(jī) 第十四張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202214通信軟件設(shè)計(jì)1.

10、有限狀態(tài)機(jī)的基本概念2. 有限狀態(tài)機(jī)編程方法主要內(nèi)容第十五張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202215通信軟件設(shè)計(jì)確定的有限狀態(tài)機(jī)一個(gè)DFA M是一個(gè)五元組，記作 M = (S, , f, S0, Z)，其中1) S = 狀態(tài)i，S是一個(gè)有限集，其中的每一個(gè)元素稱(chēng)為一個(gè)狀態(tài)2) = 輸入字符i，是一個(gè)有窮字母表，它的每一個(gè)元素稱(chēng)為一個(gè)輸入字符3) f : S S，f 是轉(zhuǎn)換函數(shù)，表示某狀態(tài)接受某個(gè)輸入字符所到達(dá)的狀態(tài)，如：f(p,a) = q，p，qS，a4) S0 S， S0是S中的元素，是唯一的一個(gè)初態(tài) 5) ZS，且 Z ，Z是S的一個(gè)子集，是一個(gè)終態(tài)集，或叫結(jié)束集

11、 第十六張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202216通信軟件設(shè)計(jì)確定的有限狀態(tài)機(jī)左側(cè)的狀態(tài)圖，在數(shù)學(xué)上稱(chēng)作DFA，其形式化定義為：M=(S, , f, S0, Z)其中，S = 0 , 1 , 2 , 3 = a , b , c , d S0 = 0 Z = 3 f: 013abcdd2第十七張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202217通信軟件設(shè)計(jì)手工編寫(xiě)狀態(tài)機(jī) 與其他常用的設(shè)計(jì)模式有所不同，程序員想要在自己的軟件系統(tǒng)中加入狀態(tài)機(jī)時(shí)，必須再額外編寫(xiě)一部分用于邏輯控制的代碼，如果系統(tǒng)足夠復(fù)雜的話，這部分代碼實(shí)現(xiàn)和維護(hù)起來(lái)還是相當(dāng)困難的。在實(shí)現(xiàn)有限狀態(tài)機(jī)

12、時(shí)，使用switch語(yǔ)句是最簡(jiǎn)單也是最直接的一種方式，其基本思路是為狀態(tài)機(jī)中的每一種狀態(tài)都設(shè)置一個(gè)case分支，專(zhuān)門(mén)用于對(duì)該狀態(tài)進(jìn)行控制。學(xué)習(xí)doorFSM工程，如何編程實(shí)現(xiàn)有限狀態(tài)機(jī)。第十八張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202218通信軟件設(shè)計(jì)手工編寫(xiě)狀態(tài)機(jī)在很長(zhǎng)一段時(shí)期內(nèi)，使用switch語(yǔ)句一直是實(shí)現(xiàn)有限狀態(tài)機(jī)的唯一方法，甚至像編譯器這樣復(fù)雜的軟件系統(tǒng)，大部分也都直接采用這種實(shí)現(xiàn)方式。但之后隨著狀態(tài)機(jī)應(yīng)用的逐漸深入，構(gòu)造出來(lái)的狀態(tài)機(jī)越來(lái)越復(fù)雜，這種方法也開(kāi)始面臨各種嚴(yán)峻的考驗(yàn)。如果狀態(tài)機(jī)中的狀態(tài)非常多，或者狀態(tài)之間的轉(zhuǎn)換關(guān)系異常復(fù)雜，那么簡(jiǎn)單地使用switch語(yǔ)句

13、構(gòu)造出來(lái)的狀態(tài)機(jī)將是不可維護(hù)的。第十九張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202219通信軟件設(shè)計(jì)doorFSM程序?qū)嵗?）新建一個(gè)Win32 Console Application的簡(jiǎn)單應(yīng)用程序，并利用ClassWiard建立doorFSM類(lèi)，用doorFSM實(shí)現(xiàn)狀態(tài)機(jī)。（2）編寫(xiě)doorFSM.h頭文件（3）編寫(xiě)doorFSM.cpp源程序 添加狀態(tài)、事件、轉(zhuǎn)化函數(shù)等（4）添加測(cè)試程序Test.cpp第二十張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202220通信軟件設(shè)計(jì)DoorFSM類(lèi)class DoorFSM public: enum Event Loc

14、k, Unlock, Open, Close; / Eventsprotected: void enterOpened(); void enterLocked(); void enterUnlocked(); void enterClosed(); public: enum States Closed, Unlocked, Locked, Opened; / states States doorState;public: DoorFSM() doorState = Opened; / Constructor virtual DoorFSM() / Destructor States curre

15、ntState() return doorState; / Get current FSM state, returns current FSM state void processEvent( Event e ); / perform event static const char* eventName( Event e ); / Get symbolic name of an event static const char* stateName( States s )；/ Get symbolic name of a state;第二十一張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09

16、.202221通信軟件設(shè)計(jì)doorFSM.cpp實(shí)現(xiàn)文件void DoorFSM:processEvent( Event e ) States yOld = doorState; bool pass = false; switch( yOld ) /transitions case Closed: if( e = Open ) /outcome actions doorState = Opened; pass = true; else if( e = Lock ) /outcome actions doorState = Locked; pass = true; break;case Unlo

17、cked: if( e = Lock ) /outcome actions doorState = Locked; pass = true; else if( e = Open ) /outcome actions doorState = Opened; pass = true; break; case Locked: if( e = Unlock ) /outcome actions doorState = Unlocked; pass = true; break;第二十二張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202222通信軟件設(shè)計(jì)自動(dòng)生成狀態(tài)機(jī) 為實(shí)用的軟件系統(tǒng)編寫(xiě)狀態(tài)機(jī)

18、并不是一件十分輕松的事情，特別是當(dāng)狀態(tài)機(jī)本身比較復(fù)雜的時(shí)候尤其如此。人們開(kāi)始嘗試開(kāi)發(fā)一些工具來(lái)自動(dòng)生成有限狀態(tài)機(jī)的框架代碼，而在Linux下就有一個(gè)挺不錯(cuò)的選擇FSME（Finite State Machine Editor）。FSME是一個(gè)基于Qt的有限狀態(tài)機(jī)工具，它能夠讓用戶(hù)通過(guò)圖形化的方式來(lái)對(duì)程序中所需要的狀態(tài)機(jī)進(jìn)行建模，并且還能夠自動(dòng)生成用C+或者Python實(shí)現(xiàn)的狀態(tài)機(jī)框架代碼。第二十三張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202223通信軟件設(shè)計(jì)可視化的FSME第二十四張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202224通信軟件設(shè)計(jì)狀態(tài)機(jī)建模 首先運(yùn)行fsme命令來(lái)啟動(dòng)狀態(tài)機(jī)編輯器，然后單擊工具欄上 New按鈕來(lái)創(chuàng)建一個(gè)新的狀態(tài)機(jī)。FSME中用于構(gòu)建狀態(tài)機(jī)的基本元素一共有五種：事件（Event）、輸入（Input）、輸出（Output）、狀態(tài)（State）和轉(zhuǎn)換（Transition），在界面左邊的樹(shù)形列表中可以找到其中的四種。 第二十五張，PPT共二十八頁(yè)，創(chuàng)作于2022年6月20.09.202225通信軟件設(shè)計(jì)小結(jié) 在面向?qū)ο蟮能浖到y(tǒng)中，有些對(duì)象具有非常復(fù)