有限狀態(tài)機(jī)教學(xué)課件

第五講有限狀態(tài)機(jī)1第五講有限狀態(tài)機(jī)12022/10/28通第2頁1.有限狀態(tài)機(jī)的基本概念2.有限狀態(tài)機(jī)編程方法主要內(nèi)容2022/10/22通第2頁1.有限狀態(tài)機(jī)的基本概念主要內(nèi)2022/10/28通第3頁狀態(tài)機(jī)的引入狀態(tài)機(jī)理論最初的發(fā)展在數(shù)字電路設(shè)計領(lǐng)域。在數(shù)字電路方面，根據(jù)輸出是否與輸入信號有關(guān)，狀態(tài)機(jī)可以劃分為Mealy型和Moore型狀態(tài)機(jī)。Moore型狀態(tài)機(jī)的輸出只和當(dāng)前狀態(tài)有關(guān)，和輸入無關(guān)。Mealy型狀態(tài)機(jī)的輸入是由當(dāng)前狀態(tài)和輸入共同決定。而在軟件設(shè)計領(lǐng)域，狀態(tài)機(jī)的理論儼然已經(jīng)自成一體，它經(jīng)常用來描述一些復(fù)雜的算法，表明一些算法的內(nèi)部的結(jié)構(gòu)和流程，更多的關(guān)注于程序?qū)ο蟮膱?zhí)行順序。2022/10/22通第3頁狀態(tài)機(jī)的引入狀態(tài)機(jī)理論最初的發(fā)展2022/10/28通第4頁靜態(tài)順序結(jié)構(gòu)動態(tài)結(jié)構(gòu)2022/10/22通第4頁靜態(tài)順序結(jié)構(gòu)2022/10/28通第5頁有限狀態(tài)機(jī)有限自動機(jī)（FiniteAutomataMachine）是計算機(jī)科學(xué)的重要基石，它在軟件開發(fā)領(lǐng)域內(nèi)通常被稱作有限狀態(tài)機(jī)（FiniteStateMachine），是一種應(yīng)用非常廣泛的軟件設(shè)計模式。有限狀態(tài)機(jī)的作用主要是描述對象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，以及如何響應(yīng)來自外界的各種事件。在現(xiàn)實(shí)中，有許多事情可以用有限個狀態(tài)來表達(dá)，如:紅綠燈、電話機(jī)等等。其實(shí)，在資訊領(lǐng)域中，很多事情都是由有限的狀態(tài)所組成，再由于不同的輸入而衍生出各個狀態(tài)。

2022/10/22通第5頁有限狀態(tài)機(jī)有限自動機(jī)（Finit2022/10/28通第6頁有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSM思想廣泛應(yīng)用于硬件控制電路設(shè)計，也是軟件上常用的一種處理方法(軟件上稱為FMM--有限消息機(jī))。它把復(fù)雜的控制邏輯分解成有限個穩(wěn)定狀態(tài)，在每個狀態(tài)上判斷事件，變連續(xù)處理為離散數(shù)字處理，符合計算機(jī)的工作特點(diǎn)。同時，因?yàn)橛邢逘顟B(tài)機(jī)具有有限個狀態(tài)，所以可以在實(shí)際的工程上實(shí)現(xiàn)。但這并不意味著其只能進(jìn)行有限次的處理，相反，有限狀態(tài)機(jī)是閉環(huán)系統(tǒng)，有限無窮，可以用有限的狀態(tài)，處理無窮的事務(wù)。

2022/10/22通第6頁有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSM思想廣2022/10/28通第7頁有限狀態(tài)機(jī)—例1紅綠燈紅綠燈運(yùn)作的原理相當(dāng)簡單，從一開始綠燈，經(jīng)過一段時間后，將變?yōu)辄S燈，再隔一會兒，就會變成紅燈，如此不斷反覆。其FSM如下。2022/10/22通第7頁有限狀態(tài)機(jī)—例1紅綠燈2022/10/28通第8頁有限狀態(tài)機(jī)—例2自動販?zhǔn)蹤C(jī)假設(shè)有簡單的一自動販賣機(jī)販?zhǔn)蹆深惿唐?，一類售價20元，另一類售價50元。如果該販賣機(jī)只能辨識10元及50元硬幣。一開始機(jī)器處于Hello的狀態(tài)，當(dāng)投入10元時，機(jī)器會進(jìn)入余額不足的狀態(tài)，直到投入的金額大于20元為止。如果一次投入50元，則可以選擇所有的產(chǎn)品，否則就只能選擇20元的產(chǎn)品。完成選擇后，將會賣出商品并且找回剩余的零錢，隨后，機(jī)器又將返回初始的狀態(tài)。其FSM如下。2022/10/22通第8頁有限狀態(tài)機(jī)—例2自動販?zhǔn)蹤C(jī)2022/10/28通第9頁基本概念在描述有限狀態(tài)機(jī)時，常會碰到的幾個基本概念：狀態(tài)（State）指的是對象在其生命周期中的一種狀況，處于某個特定狀態(tài)中的對象必然會滿足某些條件、執(zhí)行某些動作或者是等待某些事件。事件（Event）指的是在時間和空間上占有一定位置，并且對狀態(tài)機(jī)來講是有意義的那些事情。事件通常會引起狀態(tài)的變遷，促使?fàn)顟B(tài)機(jī)從一種狀態(tài)切換到另一種狀態(tài)。轉(zhuǎn)換（Transition）指的是兩個狀態(tài)之間的一種關(guān)系，表明對象將在第一個狀態(tài)中執(zhí)行一定的動作，并將在某個事件發(fā)生同時某個特定條件滿足時進(jìn)入第二個狀態(tài)。動作（Action）指的是狀態(tài)機(jī)中可以執(zhí)行的那些原子操作，所謂原子操作指的是它們在運(yùn)行的過程中不能被其他消息所中斷，必須一直執(zhí)行下去。

2022/10/22通第9頁基本概念在描述有限狀態(tài)機(jī)時，常會2022/10/28通第10頁有限狀態(tài)機(jī)模型通信協(xié)議建?；境霭l(fā)點(diǎn)：認(rèn)為通信協(xié)議主要是由響應(yīng)多個“事件”的相對簡單的處理過程組成。狀態(tài)轉(zhuǎn)移圖優(yōu)點(diǎn)：簡單明了，比較精確。缺點(diǎn)：對許多復(fù)雜的協(xié)議，事件數(shù)和狀態(tài)數(shù)會劇增，處理困難。2022/10/22通第10頁有限狀態(tài)機(jī)模型通信協(xié)議建模2022/10/28通第11頁為什么使用有限狀態(tài)機(jī)在面向?qū)ο蟮能浖到y(tǒng)中，一個對象無論多么簡單或者多么復(fù)雜，都必然會經(jīng)歷一個從開始創(chuàng)建到最終消亡的完整過程，這通常被稱為對象的生命周期。對象在其生命期內(nèi)是不可能完全孤立的，它必須通過發(fā)送消息來影響其它對象，或者通過接受消息來改變自身。2022/10/22通第11頁為什么使用有限狀態(tài)機(jī)在面向?qū)ο?022/10/28通第12頁為什么使用有限狀態(tài)機(jī)在銀行客戶管理系統(tǒng)中，客戶類（Customer）的實(shí)例在需要的時候，可能會調(diào)用帳戶（Account）類中定義的getBalance()方法。在這種簡單的情況下，類Customer并不需要一個有限狀態(tài)機(jī)來描述自己的行為，主要原因在于它當(dāng)前的行為并不依賴于過去的某個狀態(tài)。并不是所有情況都會如此簡單，事實(shí)上許多實(shí)用的軟件系統(tǒng)都必須維護(hù)一兩個非常關(guān)鍵的對象，它們通常具有非常復(fù)雜的狀態(tài)轉(zhuǎn)換關(guān)系，而且需要對來自外部的各種事件進(jìn)行響應(yīng)。例如，在VoIP電話系統(tǒng)（找狀態(tài)圖）中，電話類（Telephone）的實(shí)例必須能夠響應(yīng)來自對方的隨機(jī)呼叫，來自用戶的按鍵事件，以及來自網(wǎng)絡(luò)的信令等。在處理這些消息時，類Telephone所要采取的行為完全依賴于它當(dāng)前所處的狀態(tài)，此時使用狀態(tài)機(jī)將是一個不錯的選擇。2022/10/22通第12頁為什么使用有限狀態(tài)機(jī)在銀行客戶2022/10/28通第13頁為什么使用有限狀態(tài)機(jī)游戲引擎是有限狀態(tài)機(jī)最為成功的應(yīng)用領(lǐng)域之一，由于設(shè)計良好的狀態(tài)機(jī)能夠被用來取代部分的人工智能算法，因此游戲中的每個角色或者器件都有可能內(nèi)嵌一個狀態(tài)機(jī)?？紤]RPG（Role-playingGame）游戲中城門這樣一個簡單的對象，它具有打開（Opened）、關(guān)閉（Closed）、上鎖（Locked）、解鎖（Unlocked）四種狀態(tài)。當(dāng)玩家到達(dá)一個處于狀態(tài)Locked的門時，如果此時他已經(jīng)找到了用來開門的鑰匙，那么他就可以利用它將門的當(dāng)前狀態(tài)轉(zhuǎn)變?yōu)閁nlocked，進(jìn)一步還可以通過旋轉(zhuǎn)門上的把手將其狀態(tài)轉(zhuǎn)變?yōu)镺pened，從而成功進(jìn)入城內(nèi)。2022/10/22通第13頁為什么使用有限狀態(tài)機(jī)游戲引擎是2022/10/28通第14頁控制城門的狀態(tài)機(jī)2022/10/22通第14頁控制城門的狀態(tài)機(jī)2022/10/28通第15頁1.有限狀態(tài)機(jī)的基本概念2.有限狀態(tài)機(jī)編程方法主要內(nèi)容2022/10/22通第15頁1.有限狀態(tài)機(jī)的基本概念主要2022/10/28通第16頁確定的有限狀態(tài)機(jī)一個DFAM是一個五元組，記作M=(S,,f,S0,Z)，其中1)S={狀態(tài)i}，S是一個有限集，其中的每一個元素稱為一個狀態(tài)2)={輸入字符i}，是一個有窮字母表，它的每一個元素稱為一個輸入字符3)f:S×→S，f是轉(zhuǎn)換函數(shù)，表示某狀態(tài)接受某個輸入字符所到達(dá)的狀態(tài)，如：f(p,a)=q，p，qS，a4)S0S，S0是S中的元素，是唯一的一個初態(tài)5)ZS，且Z，Z是S的一個子集，是一個終態(tài)集，或叫結(jié)束集2022/10/22通第16頁確定的有限狀態(tài)機(jī)一個DFAM2022/10/28通第17頁確定的有限狀態(tài)機(jī)左側(cè)的狀態(tài)圖，在數(shù)學(xué)上稱作DFA，其形式化定義為：M=(S,,f,S0,Z)其中，S={0,1,2,3}={a,b,c,d}S0=0Z={3}源狀態(tài)輸入目的狀態(tài)0a10C21d11b32d3f:

013abcdd22022/10/22通第17頁確定的有限狀態(tài)機(jī)左側(cè)的狀態(tài)圖，2022/10/28通第18頁手工編寫狀態(tài)機(jī)與其他常用的設(shè)計模式有所不同，程序員想要在自己的軟件系統(tǒng)中加入狀態(tài)機(jī)時，必須再額外編寫一部分用于邏輯控制的代碼，如果系統(tǒng)足夠復(fù)雜的話，這部分代碼實(shí)現(xiàn)和維護(hù)起來還是相當(dāng)困難的。在實(shí)現(xiàn)有限狀態(tài)機(jī)時，使用switch語句是最簡單也是最直接的一種方式，其基本思路是為狀態(tài)機(jī)中的每一種狀態(tài)都設(shè)置一個case分支，專門用于對該狀態(tài)進(jìn)行控制。學(xué)習(xí)doorFSM工程，如何編程實(shí)現(xiàn)有限狀態(tài)機(jī)。2022/10/22通第18頁手工編寫狀態(tài)機(jī)與其他常用的設(shè)2022/10/28通第19頁手工編寫狀態(tài)機(jī)在很長一段時期內(nèi)，使用switch語句一直是實(shí)現(xiàn)有限狀態(tài)機(jī)的唯一方法，甚至像編譯器這樣復(fù)雜的軟件系統(tǒng)，大部分也都直接采用這種實(shí)現(xiàn)方式。但之后隨著狀態(tài)機(jī)應(yīng)用的逐漸深入，構(gòu)造出來的狀態(tài)機(jī)越來越復(fù)雜，這種方法也開始面臨各種嚴(yán)峻的考驗(yàn)。如果狀態(tài)機(jī)中的狀態(tài)非常多，或者狀態(tài)之間的轉(zhuǎn)換關(guān)系異常復(fù)雜，那么簡單地使用switch語句構(gòu)造出來的狀態(tài)機(jī)將是不可維護(hù)的。2022/10/22通第19頁手工編寫狀態(tài)機(jī)在很長一段時期內(nèi)2022/10/28通第20頁doorFSM程序?qū)嵗?）新建一個Win32ConsoleApplication的簡單應(yīng)用程序，并利用ClassWiard建立doorFSM類，用doorFSM實(shí)現(xiàn)狀態(tài)機(jī)。（2）編寫doorFSM.h頭文件（3）編寫doorFSM.cpp源程序添加狀態(tài)、事件、轉(zhuǎn)化函數(shù)等（4）添加測試程序Test.cpp2022/10/22通第20頁doorFSM程序?qū)嵗?）新2022/10/28通第21頁DoorFSM類classDoorFSM{public:enumEvent{Lock,Unlock,Open,Close};//Eventsprotected:voidenterOpened();voidenterLocked();voidenterUnlocked();voidenterClosed();public:enumStates{Closed,Unlocked,Locked,Opened};//statesStatesdoorState;public:DoorFSM(){doorState=Opened;}//Constructorvirtual~DoorFSM(){}//DestructorStatescurrentState(){returndoorState;}//GetcurrentFSMstate,returnscurrentFSMstatevoidprocessEvent(Evente);//performeventstaticconstchar*eventName(Evente);//Getsymbolicnameofaneventstaticconstchar*stateName(Statess)；//Getsymbolicnameofastate};2022/10/22通第21頁DoorFSM類classD2022/10/28通第22頁doorFSM.cpp實(shí)現(xiàn)文件voidDoorFSM::processEvent(Evente){StatesyOld=doorState;boolpass=false;switch(yOld){//transitionscaseClosed:if(e==Open) {//outcomeactionsdoorState=Opened;pass=true;}elseif(e==Lock) {//outcomeactionsdoorState=Locked;pass=true;}break;caseUnlocked:if(e==Lock){//outcomeactionsdoorState=Locked;pass=true;}elseif(e==Open) {//outcomeactionsdoorState=Opened;pass=true;}break;caseLocked:if(e==Unlock) {//outcomeactionsdoorState=Unlocked;pass=true;}break;2022/10/22通第22頁doorFSM.cpp實(shí)現(xiàn)文件2022/10/28通第23頁自動生成狀態(tài)機(jī)為實(shí)用的軟件系統(tǒng)編寫狀態(tài)機(jī)并不是一件十分輕松的事情，特別是當(dāng)狀態(tài)機(jī)本身比較復(fù)雜的時候尤其如此。人們開始嘗試開發(fā)一些工具來自動生成有限狀態(tài)機(jī)的框架代碼，而在Linux下就有一個挺不錯的選擇──FSME（FiniteStateMachineEditor）。FSME是一個基于Qt的有限狀態(tài)機(jī)工具，它能夠讓用戶通過圖形化的方式來對程序中所需要的狀態(tài)機(jī)進(jìn)行建模，并且還能夠自動生成用C++或者Python實(shí)現(xiàn)的狀態(tài)機(jī)框架代碼。2022/10/22通第23頁自動生成狀態(tài)機(jī)為實(shí)用的軟件系2022/10/28通第24頁可視化的FSME2022/10/22通第24頁可視化的FSME2022/10/28通第25頁狀態(tài)機(jī)建模首先運(yùn)行fsme命令來啟動狀態(tài)機(jī)編輯器，然后單擊工具欄上""New"按鈕來創(chuàng)建一個新的狀態(tài)機(jī)。FSME中用于構(gòu)建狀態(tài)機(jī)的基本元素一共有五種：事件（Event）、輸入（Input）、輸出（Output）、狀態(tài)（State）和轉(zhuǎn)換（Transition），在界面左邊的樹形列表中可以找到其中的四種。2022/10/22通第25頁狀態(tài)機(jī)建模2022/10/28通第26頁小結(jié)在面向?qū)ο蟮能浖到y(tǒng)中，有些對象具有非常復(fù)雜的生命周期模型，使用有限狀態(tài)機(jī)是描述這類對象最好的方法。作為一種軟件設(shè)計模式，有限狀態(tài)機(jī)的概念雖然不算復(fù)雜，實(shí)現(xiàn)起來也并不困難，但它的問題是當(dāng)狀態(tài)機(jī)的模型復(fù)雜到一定的程度之后，會帶來實(shí)現(xiàn)和維護(hù)上的困難。FSME是一個可視化的有限狀態(tài)機(jī)建模工具，而且支持狀態(tài)機(jī)框架代碼的自動生成，借助它可以更加輕松地構(gòu)建基于有限狀態(tài)機(jī)的應(yīng)用系統(tǒng)。2022/10/22通第26頁小結(jié)在面向?qū)ο蟮能浖到y(tǒng)中，2022/10/28通第27頁練習(xí)：2022/10/22通第27頁練習(xí)：2022/10/28通第28頁實(shí)驗(yàn)要求上機(jī)內(nèi)容編寫一個成績轉(zhuǎn)換函數(shù)，要求：1)用戶輸入分?jǐn)?shù)，程序自動轉(zhuǎn)化成相應(yīng)的等級。2)分?jǐn)?shù)≥90，等級為優(yōu)90＞分?jǐn)?shù)≥80，等級為良80＞分?jǐn)?shù)≥70，等級為中70＞分?jǐn)?shù)≥60，等級為及格60＞分?jǐn)?shù)，等級為不及格思考題舉例說明有限狀態(tài)機(jī)在生活中的應(yīng)用，并畫出其狀態(tài)圖。2022/10/22通第28頁實(shí)驗(yàn)要求上機(jī)內(nèi)容第五講有限狀態(tài)機(jī)29第五講有限狀態(tài)機(jī)12022/10/28通第30頁1.有限狀態(tài)機(jī)的基本概念2.有限狀態(tài)機(jī)編程方法主要內(nèi)容2022/10/22通第2頁1.有限狀態(tài)機(jī)的基本概念主要內(nèi)2022/10/28通第31頁狀態(tài)機(jī)的引入狀態(tài)機(jī)理論最初的發(fā)展在數(shù)字電路設(shè)計領(lǐng)域。在數(shù)字電路方面，根據(jù)輸出是否與輸入信號有關(guān)，狀態(tài)機(jī)可以劃分為Mealy型和Moore型狀態(tài)機(jī)。Moore型狀態(tài)機(jī)的輸出只和當(dāng)前狀態(tài)有關(guān)，和輸入無關(guān)。Mealy型狀態(tài)機(jī)的輸入是由當(dāng)前狀態(tài)和輸入共同決定。而在軟件設(shè)計領(lǐng)域，狀態(tài)機(jī)的理論儼然已經(jīng)自成一體，它經(jīng)常用來描述一些復(fù)雜的算法，表明一些算法的內(nèi)部的結(jié)構(gòu)和流程，更多的關(guān)注于程序?qū)ο蟮膱?zhí)行順序。2022/10/22通第3頁狀態(tài)機(jī)的引入狀態(tài)機(jī)理論最初的發(fā)展2022/10/28通第32頁靜態(tài)順序結(jié)構(gòu)動態(tài)結(jié)構(gòu)2022/10/22通第4頁靜態(tài)順序結(jié)構(gòu)2022/10/28通第33頁有限狀態(tài)機(jī)有限自動機(jī)（FiniteAutomataMachine）是計算機(jī)科學(xué)的重要基石，它在軟件開發(fā)領(lǐng)域內(nèi)通常被稱作有限狀態(tài)機(jī)（FiniteStateMachine），是一種應(yīng)用非常廣泛的軟件設(shè)計模式。有限狀態(tài)機(jī)的作用主要是描述對象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，以及如何響應(yīng)來自外界的各種事件。在現(xiàn)實(shí)中，有許多事情可以用有限個狀態(tài)來表達(dá)，如:紅綠燈、電話機(jī)等等。其實(shí)，在資訊領(lǐng)域中，很多事情都是由有限的狀態(tài)所組成，再由于不同的輸入而衍生出各個狀態(tài)。

2022/10/22通第5頁有限狀態(tài)機(jī)有限自動機(jī)（Finit2022/10/28通第34頁有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSM思想廣泛應(yīng)用于硬件控制電路設(shè)計，也是軟件上常用的一種處理方法(軟件上稱為FMM--有限消息機(jī))。它把復(fù)雜的控制邏輯分解成有限個穩(wěn)定狀態(tài)，在每個狀態(tài)上判斷事件，變連續(xù)處理為離散數(shù)字處理，符合計算機(jī)的工作特點(diǎn)。同時，因?yàn)橛邢逘顟B(tài)機(jī)具有有限個狀態(tài)，所以可以在實(shí)際的工程上實(shí)現(xiàn)。但這并不意味著其只能進(jìn)行有限次的處理，相反，有限狀態(tài)機(jī)是閉環(huán)系統(tǒng)，有限無窮，可以用有限的狀態(tài)，處理無窮的事務(wù)。

2022/10/22通第6頁有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSM思想廣2022/10/28通第35頁有限狀態(tài)機(jī)—例1紅綠燈紅綠燈運(yùn)作的原理相當(dāng)簡單，從一開始綠燈，經(jīng)過一段時間后，將變?yōu)辄S燈，再隔一會兒，就會變成紅燈，如此不斷反覆。其FSM如下。2022/10/22通第7頁有限狀態(tài)機(jī)—例1紅綠燈2022/10/28通第36頁有限狀態(tài)機(jī)—例2自動販?zhǔn)蹤C(jī)假設(shè)有簡單的一自動販賣機(jī)販?zhǔn)蹆深惿唐?，一類售價20元，另一類售價50元。如果該販賣機(jī)只能辨識10元及50元硬幣。一開始機(jī)器處于Hello的狀態(tài)，當(dāng)投入10元時，機(jī)器會進(jìn)入余額不足的狀態(tài)，直到投入的金額大于20元為止。如果一次投入50元，則可以選擇所有的產(chǎn)品，否則就只能選擇20元的產(chǎn)品。完成選擇后，將會賣出商品并且找回剩余的零錢，隨后，機(jī)器又將返回初始的狀態(tài)。其FSM如下。2022/10/22通第8頁有限狀態(tài)機(jī)—例2自動販?zhǔn)蹤C(jī)2022/10/28通第37頁基本概念在描述有限狀態(tài)機(jī)時，常會碰到的幾個基本概念：狀態(tài)（State）指的是對象在其生命周期中的一種狀況，處于某個特定狀態(tài)中的對象必然會滿足某些條件、執(zhí)行某些動作或者是等待某些事件。事件（Event）指的是在時間和空間上占有一定位置，并且對狀態(tài)機(jī)來講是有意義的那些事情。事件通常會引起狀態(tài)的變遷，促使?fàn)顟B(tài)機(jī)從一種狀態(tài)切換到另一種狀態(tài)。轉(zhuǎn)換（Transition）指的是兩個狀態(tài)之間的一種關(guān)系，表明對象將在第一個狀態(tài)中執(zhí)行一定的動作，并將在某個事件發(fā)生同時某個特定條件滿足時進(jìn)入第二個狀態(tài)。動作（Action）指的是狀態(tài)機(jī)中可以執(zhí)行的那些原子操作，所謂原子操作指的是它們在運(yùn)行的過程中不能被其他消息所中斷，必須一直執(zhí)行下去。

2022/10/22通第9頁基本概念在描述有限狀態(tài)機(jī)時，常會2022/10/28通第38頁有限狀態(tài)機(jī)模型通信協(xié)議建?；境霭l(fā)點(diǎn)：認(rèn)為通信協(xié)議主要是由響應(yīng)多個“事件”的相對簡單的處理過程組成。狀態(tài)轉(zhuǎn)移圖優(yōu)點(diǎn)：簡單明了，比較精確。缺點(diǎn)：對許多復(fù)雜的協(xié)議，事件數(shù)和狀態(tài)數(shù)會劇增，處理困難。2022/10/22通第10頁有限狀態(tài)機(jī)模型通信協(xié)議建模2022/10/28通第39頁為什么使用有限狀態(tài)機(jī)在面向?qū)ο蟮能浖到y(tǒng)中，一個對象無論多么簡單或者多么復(fù)雜，都必然會經(jīng)歷一個從開始創(chuàng)建到最終消亡的完整過程，這通常被稱為對象的生命周期。對象在其生命期內(nèi)是不可能完全孤立的，它必須通過發(fā)送消息來影響其它對象，或者通過接受消息來改變自身。2022/10/22通第11頁為什么使用有限狀態(tài)機(jī)在面向?qū)ο?022/10/28通第40頁為什么使用有限狀態(tài)機(jī)在銀行客戶管理系統(tǒng)中，客戶類（Customer）的實(shí)例在需要的時候，可能會調(diào)用帳戶（Account）類中定義的getBalance()方法。在這種簡單的情況下，類Customer并不需要一個有限狀態(tài)機(jī)來描述自己的行為，主要原因在于它當(dāng)前的行為并不依賴于過去的某個狀態(tài)。并不是所有情況都會如此簡單，事實(shí)上許多實(shí)用的軟件系統(tǒng)都必須維護(hù)一兩個非常關(guān)鍵的對象，它們通常具有非常復(fù)雜的狀態(tài)轉(zhuǎn)換關(guān)系，而且需要對來自外部的各種事件進(jìn)行響應(yīng)。例如，在VoIP電話系統(tǒng)（找狀態(tài)圖）中，電話類（Telephone）的實(shí)例必須能夠響應(yīng)來自對方的隨機(jī)呼叫，來自用戶的按鍵事件，以及來自網(wǎng)絡(luò)的信令等。在處理這些消息時，類Telephone所要采取的行為完全依賴于它當(dāng)前所處的狀態(tài)，此時使用狀態(tài)機(jī)將是一個不錯的選擇。2022/10/22通第12頁為什么使用有限狀態(tài)機(jī)在銀行客戶2022/10/28通第41頁為什么使用有限狀態(tài)機(jī)游戲引擎是有限狀態(tài)機(jī)最為成功的應(yīng)用領(lǐng)域之一，由于設(shè)計良好的狀態(tài)機(jī)能夠被用來取代部分的人工智能算法，因此游戲中的每個角色或者器件都有可能內(nèi)嵌一個狀態(tài)機(jī)?？紤]RPG（Role-playingGame）游戲中城門這樣一個簡單的對象，它具有打開（Opened）、關(guān)閉（Closed）、上鎖（Locked）、解鎖（Unlocked）四種狀態(tài)。當(dāng)玩家到達(dá)一個處于狀態(tài)Locked的門時，如果此時他已經(jīng)找到了用來開門的鑰匙，那么他就可以利用它將門的當(dāng)前狀態(tài)轉(zhuǎn)變?yōu)閁nlocked，進(jìn)一步還可以通過旋轉(zhuǎn)門上的把手將其狀態(tài)轉(zhuǎn)變?yōu)镺pened，從而成功進(jìn)入城內(nèi)。2022/10/22通第13頁為什么使用有限狀態(tài)機(jī)游戲引擎是2022/10/28通第42頁控制城門的狀態(tài)機(jī)2022/10/22通第14頁控制城門的狀態(tài)機(jī)2022/10/28通第43頁1.有限狀態(tài)機(jī)的基本概念2.有限狀態(tài)機(jī)編程方法主要內(nèi)容2022/10/22通第15頁1.有限狀態(tài)機(jī)的基本概念主要2022/10/28通第44頁確定的有限狀態(tài)機(jī)一個DFAM是一個五元組，記作M=(S,,f,S0,Z)，其中1)S={狀態(tài)i}，S是一個有限集，其中的每一個元素稱為一個狀態(tài)2)={輸入字符i}，是一個有窮字母表，它的每一個元素稱為一個輸入字符3)f:S×→S，f是轉(zhuǎn)換函數(shù)，表示某狀態(tài)接受某個輸入字符所到達(dá)的狀態(tài)，如：f(p,a)=q，p，qS，a4)S0S，S0是S中的元素，是唯一的一個初態(tài)5)ZS，且Z，Z是S的一個子集，是一個終態(tài)集，或叫結(jié)束集2022/10/22通第16頁確定的有限狀態(tài)機(jī)一個DFAM2022/10/28通第45頁確定的有限狀態(tài)機(jī)左側(cè)的狀態(tài)圖，在數(shù)學(xué)上稱作DFA，其形式化定義為：M=(S,,f,S0,Z)其中，S={0,1,2,3}={a,b,c,d}S0=0Z={3}源狀態(tài)輸入目的狀態(tài)0a10C21d11b32d3f:

013abcdd22022/10/22通第17頁確定的有限狀態(tài)機(jī)左側(cè)的狀態(tài)圖，2022/10/28通第46頁手工編寫狀態(tài)機(jī)與其他常用的設(shè)計模式有所不同，程序員想要在自己的軟件系統(tǒng)中加入狀態(tài)機(jī)時，必須再額外編寫一部分用于邏輯控制的代碼，如果系統(tǒng)足夠復(fù)雜的話，這部分代碼實(shí)現(xiàn)和維護(hù)起來還是相當(dāng)困難的。在實(shí)現(xiàn)有限狀態(tài)機(jī)時，使用switch語句是最簡單也是最直接的一種方式，其基本思路是為狀態(tài)機(jī)中的每一種狀態(tài)都設(shè)置一個case分支，專門用于對該狀態(tài)進(jìn)行控制。學(xué)習(xí)doorFSM工程，如何編程實(shí)現(xiàn)有限狀態(tài)機(jī)。2022/10/22通第18頁手工編寫狀態(tài)機(jī)與其他常用的設(shè)2022/10/28通第47頁手工編寫狀態(tài)機(jī)在很長一段時期內(nèi)，使用switch語句一直是實(shí)現(xiàn)有限狀態(tài)機(jī)的唯一方法，甚至像編譯器這樣復(fù)雜的軟件系統(tǒng)，大部分也都直接采用這種實(shí)現(xiàn)方式。但之后隨著狀態(tài)機(jī)應(yīng)用的逐漸深入，構(gòu)造出來的狀態(tài)機(jī)越來越復(fù)雜，這種方法也開始面臨各種嚴(yán)峻的考驗(yàn)。如果狀態(tài)機(jī)中的狀態(tài)非常多，或者狀態(tài)之間的轉(zhuǎn)換關(guān)系異常復(fù)雜，那么簡單地使用switch語句構(gòu)造出來的狀態(tài)機(jī)將是不可維護(hù)的。2022/10/22通第19頁手工編寫狀態(tài)機(jī)在很長一段時期內(nèi)2022/10/28通第48頁doorFSM程序?qū)嵗?）新建一個Win32ConsoleApplication的簡單應(yīng)用程序，并利用ClassWiard建立doorFSM類，用doorFSM實(shí)現(xiàn)狀態(tài)機(jī)。（2）編寫doorFSM.h頭文件（3）編寫doorFSM.cpp源程序添加狀態(tài)、事件、轉(zhuǎn)化函數(shù)等（4）添加測試程序Test.cpp2022/10/22通第20頁doorFSM程序?qū)嵗?）新2022/10/28通第49頁DoorFSM類classDoorFSM{public:enumEvent{Lock,Unlock,Open,Close};//Eventsprotected:voidenterOpened();voidenterLocked();voidenterUnlocked();voidenterClosed();public:enumStates{Closed,Unlocked,Locked,Opened};//statesStatesdoorState;public:DoorFSM(){doorState=Opened;}//Constructorvirtual~DoorFSM(){}//DestructorStatescurrentState(){returndoorState;}//GetcurrentFSMstate,returnscurrentFSMstatevoidprocessEvent(Evente);//performeventstaticconstchar*eventName(Evente);//Getsymbolicnameofaneventstaticconstchar*stateName(Statess)；//Getsymbolicnameofastate};2022/10/22通第21頁DoorFSM類classD2022/10/28通第50頁doorFSM.cpp實(shí)現(xiàn)文件voidDoorFSM::processEvent(Evente){StatesyOld=doorState;boolpass=false;switch(yOld){//transitionscaseClosed:if(e==Open) {//outcomeactionsdoorState=Opened;pass=true;}elseif(e==Lock) {//outcomeactionsdoorState=Locked;pass=true;}break;caseUnlocked:if(e==Lock){//outcomeactionsdoorState=Locked;pass=true;