有限狀態(tài)機(jī)應(yīng)用

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

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

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

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

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

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

7、int time)/*根據(jù)狀態(tài)、請(qǐng)求和時(shí)間條件，運(yùn)行電梯或營(yíng)業(yè)廳服務(wù)。根據(jù)狀態(tài)、請(qǐng)求和時(shí)間條件，運(yùn)行電梯或營(yíng)業(yè)廳服務(wù)。運(yùn)行服務(wù)后將改變的狀態(tài)返回。運(yùn)行服務(wù)后將改變的狀態(tài)返回。注意當(dāng)服務(wù)完一個(gè)請(qǐng)求注意當(dāng)服務(wù)完一個(gè)請(qǐng)求后，刪除該節(jié)點(diǎn)并修改頭指針！后，刪除該節(jié)點(diǎn)并修改頭指針！*/void set_fileOutput(File *fp,int time,struct STATE state, struct LIST *hp) /*將當(dāng)前時(shí)間、狀態(tài)和等待隊(duì)列的情況順序?qū)懭胛募?dāng)前時(shí)間、狀態(tài)和等待隊(duì)列的情況順序?qū)懭胛募?/ 3/24/20228輸入文件格式定義：電梯輸入文件格式定義：電梯 輸入用電梯請(qǐng)

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

9、229輸出文件格式定義：電梯輸出文件格式定義：電梯 電梯運(yùn)行結(jié)果記錄文件格式：電梯運(yùn)行結(jié)果記錄文件格式： 文本文件，每一行表示一個(gè)電梯停靠或啟動(dòng)、轉(zhuǎn)向文本文件，每一行表示一個(gè)電梯停靠或啟動(dòng)、轉(zhuǎn)向動(dòng)作，當(dāng)前樓層和目標(biāo)樓層，以及排隊(duì)的樓層請(qǐng)求。動(dòng)作，當(dāng)前樓層和目標(biāo)樓層，以及排隊(duì)的樓層請(qǐng)求。格式定義如下：格式定義如下：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 3/24/202210輸出文件格式定義：電梯輸出文件格式定義：電梯 當(dāng)前時(shí)間：程序開(kāi)始運(yùn)行的系統(tǒng)時(shí)鐘時(shí)間，單位秒。當(dāng)前時(shí)間：程序開(kāi)始運(yùn)行的系統(tǒng)時(shí)鐘時(shí)間，單位秒。 電梯狀態(tài)：電梯狀態(tài)：UP_RUN表示向上運(yùn)行、表示向上運(yùn)行、DOWN_RUN表示向下運(yùn)行、表示向下運(yùn)行、UP_STOP表示上行?？俊⒈硎旧闲型？?、DOWN_STOP表示下行停靠、表示下行?？俊DLE表示空閑。表示空閑。 電梯當(dāng)前樓層：電梯當(dāng)前樓層：1.0-9.0。?？繒r(shí)間：記錄電梯已經(jīng)。?？繒r(shí)間：記錄電梯已經(jīng)?？康臅r(shí)間?？康臅r(shí)間,單位秒。只有在?？繝顟B(tài)下，該信息單位秒。只有在停靠狀態(tài)下，該信息才大于才大于

11、0。 未響應(yīng)的樓層請(qǐng)求：按照電梯控制策略，按響應(yīng)順未響應(yīng)的樓層請(qǐng)求：按照電梯控制策略，按響應(yīng)順序?qū)⑸形错憫?yīng)的呼叫請(qǐng)求和目標(biāo)樓層列出來(lái)。是由序?qū)⑸形错憫?yīng)的呼叫請(qǐng)求和目標(biāo)樓層列出來(lái)。是由呼叫方向呼叫方向(U/D/T)和數(shù)字（和數(shù)字（19）組成的序列，中）組成的序列，中間用一個(gè)空格分割。如間用一個(gè)空格分割。如2U 5D 6T，表示，表示2層上行呼層上行呼叫、叫、5層下行呼叫、層下行呼叫、6層目標(biāo)?？俊幽繕?biāo)?？俊?3/24/202211輸入文件格式定義：銀行輸入文件格式定義：銀行 輸入用銀行請(qǐng)求文件格式：輸入用銀行請(qǐng)求文件格式： 文本文件，每一行表示一個(gè)時(shí)刻發(fā)生的客戶(hù)到達(dá)事文本文件，每一行表示一個(gè)時(shí)

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

13、口狀態(tài)和正在服務(wù)的客戶(hù)號(hào)碼，以及等待服務(wù)的客戶(hù)情況。格式定義如下：務(wù)的客戶(hù)號(hào)碼，以及等待服務(wù)的客戶(hù)情況。格式定義如下： T=,Event=,Now=, Wait= =JH ZT KX ZB XB 3/24/202213輸出文件格式定義：銀行輸出文件格式定義：銀行=00019999= = S0 表示空閑表示空閑 S1 表示服務(wù)表示服務(wù) 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)自動(dòng)機(jī)模型用有限狀態(tài)自動(dòng)機(jī)

14、模型實(shí)現(xiàn)復(fù)雜的過(guò)程控制策略實(shí)現(xiàn)復(fù)雜的過(guò)程控制策略 15什么是有限狀態(tài)自動(dòng)機(jī)？什么是有限狀態(tài)自動(dòng)機(jī)？Finite State Machine,Finite State Machine,又稱(chēng)有限狀態(tài)機(jī)或簡(jiǎn)稱(chēng)狀態(tài)機(jī)，又稱(chēng)有限狀態(tài)機(jī)或簡(jiǎn)稱(chēng)狀態(tài)機(jī)，是表示有限個(gè)狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作是表示有限個(gè)狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)模型。等行為的數(shù)學(xué)模型。 狀態(tài)：存儲(chǔ)關(guān)于過(guò)去的信息，就是說(shuō)狀態(tài)：存儲(chǔ)關(guān)于過(guò)去的信息，就是說(shuō), ,它反映從系它反映從系統(tǒng)開(kāi)始到現(xiàn)在時(shí)刻的輸入變化。統(tǒng)開(kāi)始到現(xiàn)在時(shí)刻的輸入變化。 轉(zhuǎn)移轉(zhuǎn)移: :指示狀態(tài)變更，并且用必須滿(mǎn)足來(lái)確使轉(zhuǎn)移指示狀態(tài)變更，并且用必須滿(mǎn)足來(lái)確

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

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

17、個(gè)狀態(tài)。當(dāng)前狀態(tài)和條件的組合指示出下一個(gè)狀態(tài)。 完整的動(dòng)作信息可以只使用腳注來(lái)增加。完整的動(dòng)作信息可以只使用腳注來(lái)增加。狀態(tài)轉(zhuǎn)移表狀態(tài)轉(zhuǎn)移表當(dāng)前狀態(tài)當(dāng)前狀態(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有兩個(gè)不同的類(lèi)別：接受器識(shí)別器和變換器。有兩個(gè)不同的類(lèi)別：接受器識(shí)別器和變換器。 接受器產(chǎn)生一個(gè)二元輸出，說(shuō)要么接受器產(chǎn)生一個(gè)二元輸出，說(shuō)要么“是是”要么要么“否否”來(lái)來(lái)回答輸入是否被機(jī)器接受。回答輸入是否被機(jī)器接受。 在所有輸入都被處理了的時(shí)候，在所有輸入都被處理了的時(shí)候，如果當(dāng)前狀態(tài)是接受狀態(tài)，輸入被接受；如果當(dāng)前狀態(tài)是接受狀

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

19、pening”中的進(jìn)入中的進(jìn)入動(dòng)作動(dòng)作 (E:) 開(kāi)啟電機(jī)開(kāi)門(mén)，開(kāi)啟電機(jī)開(kāi)門(mén)，在狀態(tài)在狀態(tài)“Closing”中的進(jìn)入中的進(jìn)入動(dòng)作以反方向開(kāi)啟電機(jī)關(guān)門(mén)。動(dòng)作以反方向開(kāi)啟電機(jī)關(guān)門(mén)。 狀態(tài)狀態(tài)“Opened”和和“Closed”不進(jìn)行任何動(dòng)作。不進(jìn)行任何動(dòng)作。變換器狀態(tài)機(jī)（變換器狀態(tài)機(jī)（1）q0openingcmd_opencmd_closecloseing開(kāi)門(mén)關(guān)門(mén)openedclosed 20 Mealy機(jī)機(jī)-只使用輸入動(dòng)作的只使用輸入動(dòng)作的FSM，就是說(shuō)輸出依賴(lài)于輸，就是說(shuō)輸出依賴(lài)于輸入和狀態(tài)。入和狀態(tài)。 Mealy FSM 的使用經(jīng)常導(dǎo)致?tīng)顟B(tài)數(shù)目的簡(jiǎn)約。的使用經(jīng)常導(dǎo)致?tīng)顟B(tài)數(shù)目的簡(jiǎn)約。 例：電梯

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

21、一個(gè)中，每個(gè)狀態(tài)對(duì)每個(gè)可能輸入只有精確的一個(gè)轉(zhuǎn)移。在非確定型自動(dòng)機(jī)中，給定狀態(tài)對(duì)給定轉(zhuǎn)移。在非確定型自動(dòng)機(jī)中，給定狀態(tài)對(duì)給定可能輸入可以沒(méi)有或有多于一個(gè)轉(zhuǎn)移。可能輸入可以沒(méi)有或有多于一個(gè)轉(zhuǎn)移。 這個(gè)區(qū)分在實(shí)踐而非理論中更有用，因?yàn)榇嬖谶@個(gè)區(qū)分在實(shí)踐而非理論中更有用，因?yàn)榇嬖谒惴ò讶魏嗡惴ò讶魏?NDFA 轉(zhuǎn)換成等價(jià)的轉(zhuǎn)換成等價(jià)的 DFA，盡管，盡管這種轉(zhuǎn)換一般會(huì)增加自動(dòng)機(jī)的復(fù)雜性。這種轉(zhuǎn)換一般會(huì)增加自動(dòng)機(jī)的復(fù)雜性。 22有限狀態(tài)自動(dòng)機(jī)的應(yīng)用有限狀態(tài)自動(dòng)機(jī)的應(yīng)用 有限狀態(tài)自動(dòng)機(jī)在很多不同領(lǐng)域中都是重要的，有限狀態(tài)自動(dòng)機(jī)在很多不同領(lǐng)域中都是重要的，包括電子工程、包括電子工程、 語(yǔ)言學(xué)、計(jì)算機(jī)科學(xué)、

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

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

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

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

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

27、計(jì)實(shí)例研究例例4 檢驗(yàn)輸入是否是合法的檢驗(yàn)輸入是否是合法的C語(yǔ)言注釋語(yǔ)言注釋/*/導(dǎo)論教材P172,圖10.10,注意讀程序?qū)嵗齫1:等待等待*狀態(tài)狀態(tài)q2：注釋開(kāi)始狀態(tài)：注釋開(kāi)始狀態(tài)q3: 等待等待/以結(jié)束注以結(jié)束注釋狀態(tài)釋狀態(tài)q4：已接收注釋結(jié)：已接收注釋結(jié)束狀態(tài)束狀態(tài) 29程序設(shè)計(jì)實(shí)例研究程序設(shè)計(jì)實(shí)例研究 轉(zhuǎn)換函數(shù)分析轉(zhuǎn)換函數(shù)分析 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 程序設(shè)計(jì)實(shí)例研究程序設(shè)計(jì)實(shí)例研究 轉(zhuǎn)換函數(shù)分析轉(zhuǎn)換函數(shù)分析(續(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 程序設(shè)計(jì)實(shí)例研究程序設(shè)計(jì)實(shí)例研究 例例5 去除去除C語(yǔ)言注釋語(yǔ)言注釋 32有限狀態(tài)機(jī)解題通用處理模式有限狀態(tài)機(jī)解題通用處理模式有限狀態(tài)機(jī)解題通用處理模式有限狀態(tài)機(jī)解題通用處理模式

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