有限狀態(tài)機應用

1、 1大作業(yè)大作業(yè)-文件文件IO版本版本設計思路設計思路 1/29/20222大作業(yè)文件IO版本模塊結構圖模型模型內部狀態(tài)控制器控制器策略算法結果記錄結果記錄寫入文件狀態(tài)變化事件改變狀態(tài)文件輸入文件輸入讀取請求事件時間同步時間同步 1/29/20223大作業(yè)文件IO版本程序框架/* 大作業(yè)文件大作業(yè)文件IO版本的程序主體結構版本的程序主體結構 */struct STATE /電梯或銀行的運行狀態(tài)電梯或銀行的運行狀態(tài)struct LIST /請求隊列鏈表節(jié)點請求隊列鏈表節(jié)點struct REQ /暫存每次獲得的請求事件暫存每次獲得的請求事件int main() int timeCount=0; /

2、計時器，每循環(huán)一次模擬計時器，每循環(huán)一次模擬2ms struct REQ theReq=; /暫存每次獲得的請求事件暫存每次獲得的請求事件 struct STATE preST,theST =;/保存電梯或銀行的運行狀態(tài)保存電梯或銀行的運行狀態(tài) struct LIST *headp=NULL;/存請求隊列鏈表頭指針存請求隊列鏈表頭指針 File *fpin,*fpout; 1/29/20224大作業(yè)文件IO版本程序框架 openFile(*fpin,*fpout); /打開輸入輸出文件打開輸入輸出文件 theReq=get_fileInput(fpin); /讀取第一個請求讀取第一個請求 wh

3、ile (!(endInput(fpin)&isIdle(theST)/當文件輸入結束，且電梯或營業(yè)廳空閑才退出當文件輸入結束，且電梯或營業(yè)廳空閑才退出if (theReq.time=timeCount) headp=addServList(headp,theReq,theST,1); /*當請求事件發(fā)生的時間到，添加請求事件到服當請求事件發(fā)生的時間到，添加請求事件到服務隊列中務隊列中, 策略參數為策略參數為1對應先來先服務，對應先來先服務，2對應順便對應順便服務服務*/ theReq=get_fileInput(fpin);/讀取文件中的下一個請求事件讀取文件中的下一個請求事件/en

4、d if 1/29/20225大作業(yè)文件IO版本程序框架 preST=theST;theST=runService(preST,&headp,timeCount);if (theST.state!=preST.state) set_fileOutput(fpout,timeCount,theST, headp); /*當狀態(tài)變化，將當前時間、狀態(tài)和等待隊列當狀態(tài)變化，將當前時間、狀態(tài)和等待隊列的情況寫入到文件中。的情況寫入到文件中。 */timeCount+;/end whilecloseFile(fpin,fpout); /關閉輸入輸出文件關閉輸入輸出文件return 0;/end

5、main 1/29/20226大作業(yè)文件IO版本函數接口int endInput(File *fp)/判斷文件輸入是否結束判斷文件輸入是否結束int isIdle(struct STATE state)/判斷電梯或營業(yè)廳當前狀態(tài)是否空閑判斷電梯或營業(yè)廳當前狀態(tài)是否空閑struct REQ get_fileInput(File *fp)/順序讀取文件中的一個請求事件順序讀取文件中的一個請求事件struct LIST * addServList(struct LIST *hp,struct REQ req, struct STATE state, int mode); /按照策略，將新請求插入請求

6、隊列中按照策略，將新請求插入請求隊列中struct STATE runService(struct STATE state, struct LIST *hp,int time)/*根據狀態(tài)、請求和時間條件，運行電梯或營業(yè)廳服務。根據狀態(tài)、請求和時間條件，運行電梯或營業(yè)廳服務。運行服務后將改變的狀態(tài)返回。運行服務后將改變的狀態(tài)返回。注意當服務完一個請求注意當服務完一個請求后，刪除該節(jié)點并修改頭指針！后，刪除該節(jié)點并修改頭指針！*/ 1/29/20227大作業(yè)文件IO版本函數接口struct STATE runService(struct STATE state, struct LIST *hp,

7、int time)/*根據狀態(tài)、請求和時間條件，運行電梯或營業(yè)廳服務。根據狀態(tài)、請求和時間條件，運行電梯或營業(yè)廳服務。運行服務后將改變的狀態(tài)返回。運行服務后將改變的狀態(tài)返回。注意當服務完一個請求注意當服務完一個請求后，刪除該節(jié)點并修改頭指針！后，刪除該節(jié)點并修改頭指針！*/void set_fileOutput(File *fp,int time,struct STATE state, struct LIST *hp) /*將當前時間、狀態(tài)和等待隊列的情況順序寫入文件將當前時間、狀態(tài)和等待隊列的情況順序寫入文件*/ 1/29/20228輸入文件格式定義：電梯輸入文件格式定義：電梯 輸入用電梯請

8、求文件格式：輸入用電梯請求文件格式： 文本文件，每一行表示一個時刻發(fā)生的電梯請求。文本文件，每一行表示一個時刻發(fā)生的電梯請求。格式定義如下：格式定義如下： T=,CallF=例例:T=1,CallF=4UT=2,CallF=4U 5T請求發(fā)生時間：按程序運行的系統時鐘時間，單請求發(fā)生時間：按程序運行的系統時鐘時間，單位秒位秒.樓層請求：由呼叫方向樓層請求：由呼叫方向(U/D/T)和數字（和數字（19）組）組成，同時有多個請求時用空格分割。如成，同時有多個請求時用空格分割。如2U 5D 6T，表示，表示2層上行呼叫、層上行呼叫、5層下行呼叫、層下行呼叫、6層目標層目標?？?。?？?。 1/29/20

9、229輸出文件格式定義：電梯輸出文件格式定義：電梯 電梯運行結果記錄文件格式：電梯運行結果記錄文件格式： 文本文件，每一行表示一個電梯?？炕騿?、轉向文本文件，每一行表示一個電梯?？炕騿?、轉向動作，當前樓層和目標樓層，以及排隊的樓層請求。動作，當前樓層和目標樓層，以及排隊的樓層請求。格式定義如下：格式定義如下：T=,State=,NowF=,GoalF=,StopT=, WaitF=例例:T=3,State=UP_RUN,NowF=1.0,GoalF=3, StopT=0,WaitF=4U 5D 6TT=3,State=UP,NowF=1.0,GoalF=3,StopT=0, WaitF=4

10、U 5T 6U 9D 8D 1/29/202210輸出文件格式定義：電梯輸出文件格式定義：電梯 當前時間：程序開始運行的系統時鐘時間，單位秒。當前時間：程序開始運行的系統時鐘時間，單位秒。 電梯狀態(tài)：電梯狀態(tài)：UP_RUN表示向上運行、表示向上運行、DOWN_RUN表示向下運行、表示向下運行、UP_STOP表示上行停靠、表示上行?？?、DOWN_STOP表示下行?？?、表示下行?？?、IDLE表示空閑。表示空閑。 電梯當前樓層：電梯當前樓層：1.0-9.0。?？繒r間：記錄電梯已經。?？繒r間：記錄電梯已經停靠的時間?？康臅r間,單位秒。只有在?？繝顟B(tài)下，該信息單位秒。只有在?？繝顟B(tài)下，該信息才大于才大于

11、0。 未響應的樓層請求：按照電梯控制策略，按響應順未響應的樓層請求：按照電梯控制策略，按響應順序將尚未響應的呼叫請求和目標樓層列出來。是由序將尚未響應的呼叫請求和目標樓層列出來。是由呼叫方向呼叫方向(U/D/T)和數字（和數字（19）組成的序列，中）組成的序列，中間用一個空格分割。如間用一個空格分割。如2U 5D 6T，表示，表示2層上行呼層上行呼叫、叫、5層下行呼叫、層下行呼叫、6層目標?？?。層目標?？?。 1/29/202211輸入文件格式定義：銀行輸入文件格式定義：銀行 輸入用銀行請求文件格式：輸入用銀行請求文件格式： 文本文件，每一行表示一個時刻發(fā)生的客戶到達事文本文件，每一行表示一個時

12、刻發(fā)生的客戶到達事件、窗口休息請求或下班指令。格式定義如下：件、窗口休息請求或下班指令。格式定義如下： T=,Req=C | W| Q例例:T=1,Req=C5T=6,Req=W3T=200,Req=Q250時間：按程序運行的系統時鐘時間，單位秒時間：按程序運行的系統時鐘時間，單位秒. 1/29/202212輸出文件格式定義：銀行輸出文件格式定義：銀行 銀行運行結果記錄文件格式：銀行運行結果記錄文件格式： 文本文件，每一行表示一個營業(yè)廳窗口的叫號、暫停休息、文本文件，每一行表示一個營業(yè)廳窗口的叫號、暫停休息、準備下班、進入空閑、下班等動作，各窗口狀態(tài)和正在服準備下班、進入空閑、下班等動作，各窗

13、口狀態(tài)和正在服務的客戶號碼，以及等待服務的客戶情況。格式定義如下：務的客戶號碼，以及等待服務的客戶情況。格式定義如下： T=,Event=,Now=, Wait= =JH ZT KX ZB XB 1/29/202213輸出文件格式定義：銀行輸出文件格式定義：銀行=00019999= = S0 表示空閑表示空閑 S1 表示服務表示服務 S2 表示暫停表示暫停=策略策略1： 策略策略2： 例例:T=3,Event=JH W2 C0009,Now=W1 S1 C0004 W2 S2 C0000 W3 S0 C0000,Wait=Q19 F0010 L0028 14用有限狀態(tài)自動機模型用有限狀態(tài)自動機

14、模型實現復雜的過程控制策略實現復雜的過程控制策略 15什么是有限狀態(tài)自動機？什么是有限狀態(tài)自動機？Finite State Machine,Finite State Machine,又稱有限狀態(tài)機或簡稱狀態(tài)機，又稱有限狀態(tài)機或簡稱狀態(tài)機，是表示有限個狀態(tài)以及在這些狀態(tài)之間的轉移和動作是表示有限個狀態(tài)以及在這些狀態(tài)之間的轉移和動作等行為的數學模型。等行為的數學模型。 狀態(tài)：存儲關于過去的信息，就是說狀態(tài)：存儲關于過去的信息，就是說, ,它反映從系它反映從系統開始到現在時刻的輸入變化。統開始到現在時刻的輸入變化。 轉移轉移: :指示狀態(tài)變更，并且用必須滿足來確使轉移指示狀態(tài)變更，并且用必須滿足來確

15、使轉移發(fā)生的條件來描述它。發(fā)生的條件來描述它。 動作動作: :是在給定時刻要進行的活動的描述。有多種是在給定時刻要進行的活動的描述。有多種類型的動作：類型的動作：n進入動作（進入動作（Entry actionEntry action）- -在進入狀態(tài)時進行在進入狀態(tài)時進行 n退出動作退出動作 - -在退出狀態(tài)時進行在退出狀態(tài)時進行 n輸入動作輸入動作 - -依賴于當前狀態(tài)和輸入條件進行依賴于當前狀態(tài)和輸入條件進行 n轉移動作轉移動作 - -在進行特定轉移時進行在進行特定轉移時進行 16 為了描述一個有限狀態(tài)機的工作狀況，可采用為了描述一個有限狀態(tài)機的工作狀況，可采用。狀態(tài)轉換圖是一個有向圖，圖

16、中的每個節(jié)。狀態(tài)轉換圖是一個有向圖，圖中的每個節(jié)點表示一種狀態(tài)，一條邊（或?。┍硎疽粋€轉換關點表示一種狀態(tài)，一條邊（或?。┍硎疽粋€轉換關系。系。 初始狀態(tài)通常用初始狀態(tài)通常用“沒有起點的箭頭沒有起點的箭頭”指向它來表示指向它來表示。 終止狀態(tài)是機器終止狀態(tài)是機器完成了它的程序之后完成了它的程序之后的狀態(tài)，它通常表示的狀態(tài)，它通常表示為雙重圓圈。為雙重圓圈。q0q1q3q2aabbb狀態(tài)轉換圖狀態(tài)轉換圖a 17狀態(tài)表狀態(tài)表 除了狀態(tài)轉換圖以外除了狀態(tài)轉換圖以外, ,還可以使用多種類型的狀態(tài)轉還可以使用多種類型的狀態(tài)轉移表。最常見的表示如下：移表。最常見的表示如下： 當前狀態(tài)和條件的組合指示出下一

17、個狀態(tài)。當前狀態(tài)和條件的組合指示出下一個狀態(tài)。 完整的動作信息可以只使用腳注來增加。完整的動作信息可以只使用腳注來增加。狀態(tài)轉移表狀態(tài)轉移表當前狀態(tài)當前狀態(tài) 條件條件 狀態(tài)狀態(tài) A狀態(tài)狀態(tài) B狀態(tài)狀態(tài) C條件條件 X條件條件 Y狀態(tài) C條件條件 Z 18 FSMFSM有兩個不同的類別：接受器識別器和變換器。有兩個不同的類別：接受器識別器和變換器。 接受器產生一個二元輸出，說要么接受器產生一個二元輸出，說要么“是是”要么要么“否否”來來回答輸入是否被機器接受?；卮疠斎胧欠癖粰C器接受。 在所有輸入都被處理了的時候，在所有輸入都被處理了的時候，如果當前狀態(tài)是接受狀態(tài)，輸入被接受；如果當前狀態(tài)是接受狀

18、態(tài)，輸入被接受；否則被拒絕。否則被拒絕。 作為規(guī)則，輸入是符號作為規(guī)則，輸入是符號（字符）；動作不使用。（字符）；動作不使用。接受器狀態(tài)機接受器狀態(tài)機q0q1q3q2aabbbErr非非a或或ba 19 變換器使用動作基于給定輸入和或狀態(tài)生成輸出。常變換器使用動作基于給定輸入和或狀態(tài)生成輸出。常分為兩種類型：分為兩種類型：Moore機和機和Mealy機。機。 Moore機機-只使用進入動作的只使用進入動作的FSM，就是說輸出只依賴于，就是說輸出只依賴于狀態(tài)。狀態(tài)。Moore 模型的好處是行為的簡單性。模型的好處是行為的簡單性。 例：一個電梯門的例：一個電梯門的 Moore FSM。狀態(tài)狀態(tài)“O

19、pening”中的進入中的進入動作動作 (E:) 開啟電機開門，開啟電機開門，在狀態(tài)在狀態(tài)“Closing”中的進入中的進入動作以反方向開啟電機關門。動作以反方向開啟電機關門。 狀態(tài)狀態(tài)“Opened”和和“Closed”不進行任何動作。不進行任何動作。變換器狀態(tài)機（變換器狀態(tài)機（1）q0openingcmd_opencmd_closecloseing開門關門openedclosed 20 Mealy機機-只使用輸入動作的只使用輸入動作的FSM，就是說輸出依賴于輸，就是說輸出依賴于輸入和狀態(tài)。入和狀態(tài)。 Mealy FSM 的使用經常導致狀態(tài)數目的簡約。的使用經常導致狀態(tài)數目的簡約。 例：電梯

20、門的例：電梯門的Mealy FSM 有兩個輸入動作：有兩個輸入動作：“開啟電機開啟電機關門如果關門如果 command_close 下達下達”和和“反向開啟電機開門如果反向開啟電機開門如果 command_open 下達下達”。變換器狀態(tài)機（變換器狀態(tài)機（2）q0openedcmd_open/開門開門cmd_close/關門關門closed 21FSM的類型的類型 在實踐中經常使用混合模型。在實踐中經常使用混合模型。 進一步可區(qū)分為確定型（進一步可區(qū)分為確定型（DFA）和非確定型）和非確定型（NDFA、GNFA）自動機。在確定型自動機）自動機。在確定型自動機中，每個狀態(tài)對每個可能輸入只有精確的

21、一個中，每個狀態(tài)對每個可能輸入只有精確的一個轉移。在非確定型自動機中，給定狀態(tài)對給定轉移。在非確定型自動機中，給定狀態(tài)對給定可能輸入可以沒有或有多于一個轉移?？赡茌斎肟梢詻]有或有多于一個轉移。 這個區(qū)分在實踐而非理論中更有用，因為存在這個區(qū)分在實踐而非理論中更有用，因為存在算法把任何算法把任何 NDFA 轉換成等價的轉換成等價的 DFA，盡管，盡管這種轉換一般會增加自動機的復雜性。這種轉換一般會增加自動機的復雜性。 22有限狀態(tài)自動機的應用有限狀態(tài)自動機的應用 有限狀態(tài)自動機在很多不同領域中都是重要的，有限狀態(tài)自動機在很多不同領域中都是重要的，包括電子工程、包括電子工程、 語言學、計算機科學、

22、哲學、語言學、計算機科學、哲學、生物學、數學和邏輯學。有限狀態(tài)機是在自動生物學、數學和邏輯學。有限狀態(tài)機是在自動機理論和計算理論中研究的一類自動機。在計機理論和計算理論中研究的一類自動機。在計算機科學中，有限狀態(tài)機被廣泛用于算機科學中，有限狀態(tài)機被廣泛用于建模應用建模應用行為、硬件電路系統設計、軟件工程，編譯器、行為、硬件電路系統設計、軟件工程，編譯器、網絡協議、和計算與語言的研究網絡協議、和計算與語言的研究。 針對許多類型的編程問題，建立有限狀態(tài)自動針對許多類型的編程問題，建立有限狀態(tài)自動機模型，可以為分析、求解帶來很大的幫助。機模型，可以為分析、求解帶來很大的幫助。 23例例1：串口通信：

23、串口通信 兩臺微機通過串口通信兩臺微機通過串口通信, 需在兩臺機器間建立需在兩臺機器間建立好連接后，才可以傳遞數據，可以使用有限狀態(tài)自好連接后，才可以傳遞數據，可以使用有限狀態(tài)自動機，描述串口通信的狀態(tài)。動機，描述串口通信的狀態(tài)。傳輸數據傳輸數據收到收到應答應答斷開斷開連接連接發(fā)出連接請求發(fā)出連接請求q0q1q2q0：空閑狀態(tài)：空閑狀態(tài)q1: 等待應答狀態(tài)等待應答狀態(tài)q2：通信狀態(tài)：通信狀態(tài) 24例例2：打電話：打電話 (狀態(tài)機在通信領域的應用狀態(tài)機在通信領域的應用)。 在一次呼叫中，從建立連接到通話完畢，要經在一次呼叫中，從建立連接到通話完畢，要經歷摘機，撥號，應答，進行通話等過程，話機的狀

24、歷摘機，撥號，應答，進行通話等過程，話機的狀態(tài)及狀態(tài)遷移如下所示。態(tài)及狀態(tài)遷移如下所示。q0q0q1q1q2q2q3q3q4q4摘機摘機收到撥號音收到撥號音撥號撥號收應答信號收應答信號掛機掛機收齊號碼收齊號碼q0:q0:空閑狀態(tài)空閑狀態(tài)q1:q1:等待撥號音狀態(tài)等待撥號音狀態(tài)q2:q2:可以撥號狀態(tài)可以撥號狀態(tài)q3:q3:等待應答狀態(tài)等待應答狀態(tài)q4:q4:通話狀態(tài)通話狀態(tài)狀態(tài)遷移狀態(tài)遷移狀態(tài)狀態(tài) 25 接受器接受器有限狀態(tài)機的形式化定義有限狀態(tài)機的形式化定義一個五元組一個五元組其中：其中： ：有限的狀態(tài)集合；：有限的狀態(tài)集合； ：有限的輸入字母表；：有限的輸入字母表； ： 轉換函數，是轉換函

25、數，是 到到 的映射；的映射； ： 初始狀態(tài)，初始狀態(tài)， ； ： 終止狀態(tài)集，終止狀態(tài)集， ；QT0qFTQQQF 接受器的形式化定義接受器的形式化定義Qq 0),(0FqTQM（初始狀態(tài)只有一個）（初始狀態(tài)只有一個） 26aq0q1q3q2aabbb狀態(tài)集合狀態(tài)集合字母表字母表初始狀態(tài)初始狀態(tài)終止狀態(tài)集終止狀態(tài)集,3210qqqqQ ,baT 3qF 0q轉換函數轉換函數10),(qaq20),(qbq31),(qaq11),(qbq22),(qaq32),(qbq),(3aq),(3bq 例3:用于識別輸入的字符串是否是 或者 形式的有限自動機。aabnbban 27程序設計實例研究程序設

26、計實例研究應用有限狀態(tài)機模型求解問題，關鍵就是抽象出狀態(tài)，應用有限狀態(tài)機模型求解問題，關鍵就是抽象出狀態(tài)，描述出狀態(tài)轉移圖和狀態(tài)轉移函數描述出狀態(tài)轉移圖和狀態(tài)轉移函數應用有限狀態(tài)機解題步驟應用有限狀態(tài)機解題步驟1、確定輸入集、確定輸入集2、繪制狀態(tài)遷移圖（確定狀態(tài)，在每一個狀態(tài)下對輸入、繪制狀態(tài)遷移圖（確定狀態(tài)，在每一個狀態(tài)下對輸入進行分類，確定下一個狀態(tài)）進行分類，確定下一個狀態(tài)）3、確定狀態(tài)轉移函數（在某狀態(tài)下，接收到某一字符后，、確定狀態(tài)轉移函數（在某狀態(tài)下，接收到某一字符后，自動機要執(zhí)行的操作，以及遷移到的下一狀態(tài)）自動機要執(zhí)行的操作，以及遷移到的下一狀態(tài)） 28程序設計實例研究程序設

27、計實例研究例例4 檢驗輸入是否是合法的檢驗輸入是否是合法的C語言注釋語言注釋/*/導論教材P172,圖10.10,注意讀程序實例q1:等待等待*狀態(tài)狀態(tài)q2：注釋開始狀態(tài)：注釋開始狀態(tài)q3: 等待等待/以結束注以結束注釋狀態(tài)釋狀態(tài)q4：已接收注釋結：已接收注釋結束狀態(tài)束狀態(tài) 29程序設計實例研究程序設計實例研究 轉換函數分析轉換函數分析 start狀態(tài)下：狀態(tài)下：n輸入輸入/:state=q1n輸出非輸出非/:state=ERROR q1狀態(tài)下：狀態(tài)下：n輸入輸入*:state=q2n輸出非輸出非*:state=ERROR q2狀態(tài)下：狀態(tài)下：n輸入輸入*:state=q3n輸入輸入EOF：s

28、tate=ERRORn輸出其他輸出其他: state=q2 306.2 程序設計實例研究程序設計實例研究 轉換函數分析轉換函數分析(續(xù)）續(xù)） q3狀態(tài)下：狀態(tài)下：n輸入輸入*:狀態(tài)不變狀態(tài)不變n輸入輸入/:state=q4n輸入輸入EOF：state=ERRORn輸出其他輸出其他: state=q2 q4狀態(tài)下：狀態(tài)下：n輸入輸入EOF：state=ACCEPTn輸出其他輸出其他: state=ERROR 316.2 程序設計實例研究程序設計實例研究 例例5 去除去除C語言注釋語言注釋 32有限狀態(tài)機解題通用處理模式有限狀態(tài)機解題通用處理模式有限狀態(tài)機解題通用處理模式有限狀態(tài)機解題通用處理模式

29、#define START 1.int state=START;.while (state!=END) ch=getch(); switch(state) case START: if (ch=?) state=Q1; break;. 33為什么要用狀態(tài)機為什么要用狀態(tài)機?有限狀態(tài)機到底有什么好處？怎樣才算應用狀態(tài)機解題？有限狀態(tài)機到底有什么好處？怎樣才算應用狀態(tài)機解題？1、狀態(tài)機用數學模型來設計解題思路，準確可靠、簡練，、狀態(tài)機用數學模型來設計解題思路，準確可靠、簡練，而程序員僅僅依靠自己的腦力和復雜的程序結構。而程序員僅僅依靠自己的腦力和復雜的程序結構。2、狀態(tài)機模型的思路和人解決問題的思路是一致的，都、狀態(tài)機模型的思路和人解決問題的思路是一致的，都是把復雜的問題逐步分解為簡單的步驟。所以狀態(tài)機模是把復雜的問題逐步分解為簡單的步驟。所以狀態(tài)機模型是程序員的好助手，不是你的競爭對手。型是程序員的好助手，不是你的競爭對手。3、狀態(tài)機