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

1大作業(yè)-文件IO版本設(shè)計思路2/7/20232大作業(yè)文件IO版本模塊結(jié)構(gòu)圖模型內(nèi)部狀態(tài)控制器策略算法結(jié)果記錄寫入文件狀態(tài)變化事件改變狀態(tài)文件輸入讀取請求事件時間同步2/7/20233大作業(yè)文件IO版本程序框架/*大作業(yè)文件IO版本的程序主體結(jié)構(gòu)*/structSTATE{…}//電梯或銀行的運行狀態(tài)structLIST{…}//請求隊列鏈表節(jié)點structREQ{…}//暫存每次獲得的請求事件intmain(){inttimeCount=0;//計時器，每循環(huán)一次模擬2msstructREQtheReq={};//暫存每次獲得的請求事件structSTATEpreST,theST={}; //保存電梯或銀行的運行狀態(tài)structLIST*headp=NULL;//存請求隊列鏈表頭指針File*fpin,*fpout;2/7/20234大作業(yè)文件IO版本程序框架openFile(**fpin,**fpout);//打開輸入輸出文件theReq=get_fileInput(fpin);//讀取第一個請求while(!(endInput(fpin)&&isIdle(theST))){ //當(dāng)文件輸入結(jié)束，且電梯或營業(yè)廳空閑才退出 if(theReq.time==timeCount){

headp=addServList(headp,theReq,theST,1); /*當(dāng)請求事件發(fā)生的時間到，添加請求事件到服務(wù)隊列中,策略參數(shù)為1對應(yīng)先來先服務(wù)，2對應(yīng)順便服務(wù)*/ theReq=get_fileInput(fpin); //讀取文件中的下一個請求事件 }//endif

2/7/20235大作業(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)前時間、狀態(tài)和等待隊列的情況寫入到文件中。*/ timeCount++; }//endwhile closeFile(fpin,fpout);//關(guān)閉輸入輸出文件 return0;}//endmain2/7/20236大作業(yè)文件IO版本函數(shù)接口intendInput(File*fp)//判斷文件輸入是否結(jié)束intisIdle(structSTATEstate)//判斷電梯或營業(yè)廳當(dāng)前狀態(tài)是否空閑structREQget_fileInput(File*fp)//順序讀取文件中的一個請求事件structLIST*addServList(structLIST*hp,structREQreq,structSTATEstate,intmode);//按照策略，將新請求插入請求隊列中structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根據(jù)狀態(tài)、請求和時間條件，運行電梯或營業(yè)廳服務(wù)。運行服務(wù)后將改變的狀態(tài)返回。注意當(dāng)服務(wù)完一個請求后，刪除該節(jié)點并修改頭指針！*/2/7/20237大作業(yè)文件IO版本函數(shù)接口structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根據(jù)狀態(tài)、請求和時間條件，運行電梯或營業(yè)廳服務(wù)。運行服務(wù)后將改變的狀態(tài)返回。注意當(dāng)服務(wù)完一個請求后，刪除該節(jié)點并修改頭指針！*/voidset_fileOutput(File*fp,inttime,structSTATEstate,structLIST*hp)/*將當(dāng)前時間、狀態(tài)和等待隊列的情況順序?qū)懭胛募?/2/7/20238輸入文件格式定義：電梯輸入用電梯請求文件格式：文本文件，每一行表示一個時刻發(fā)生的電梯請求。格式定義如下： T=<請求發(fā)生時間>,CallF=<樓層請求><\n>例:T=1,CallF=4UT=2,CallF=4U5T請求發(fā)生時間：按程序運行的系統(tǒng)時鐘時間，單位秒.樓層請求：由呼叫方向(U/D/T)和數(shù)字（1～9）組成，同時有多個請求時用空格分割。如2U5D6T，表示2層上行呼叫、5層下行呼叫、6層目標(biāo)?？俊?/7/20239輸出文件格式定義：電梯電梯運行結(jié)果記錄文件格式：文本文件，每一行表示一個電梯停靠或啟動、轉(zhuǎn)向動作，當(dāng)前樓層和目標(biāo)樓層，以及排隊的樓層請求。格式定義如下： T=<當(dāng)前時間>,State=<電梯狀態(tài)>,NowF=<電梯當(dāng)前樓層>,GoalF=<電梯目標(biāo)樓層>,StopT=<?？繒r間>,WaitF=<未響應(yīng)的樓層請求><\n>例:T=3,State=UP_RUN,NowF=1.0,GoalF=3,StopT=0,WaitF=4U5D6TT=3,State=UP,NowF=1.0,GoalF=3,StopT=0,WaitF=4U5T6U9D8D2/7/202310輸出文件格式定義：電梯當(dāng)前時間：程序開始運行的系統(tǒng)時鐘時間，單位秒。電梯狀態(tài)：UP_RUN表示向上運行、DOWN_RUN表示向下運行、UP_STOP表示上行?？?、DOWN_STOP表示下行?？?、IDLE表示空閑。電梯當(dāng)前樓層：1.0-9.0。?？繒r間：記錄電梯已經(jīng)?？康臅r間,單位秒。只有在?？繝顟B(tài)下，該信息才大于0。未響應(yīng)的樓層請求：按照電梯控制策略，按響應(yīng)順序?qū)⑸形错憫?yīng)的呼叫請求和目標(biāo)樓層列出來。是由呼叫方向(U/D/T)和數(shù)字（1～9）組成的序列，中間用一個空格分割。如2U5D6T，表示2層上行呼叫、5層下行呼叫、6層目標(biāo)?？俊?/7/202311輸入文件格式定義：銀行輸入用銀行請求文件格式：文本文件，每一行表示一個時刻發(fā)生的客戶到達事件、窗口休息請求或下班指令。格式定義如下： T=<請求發(fā)生時間>,Req=<請求><\n> <請求>=C<客戶人數(shù)>|W<請求休息的窗口號> |Q<下班時間>例:T=1,Req=C5T=6,Req=W3T=200,Req=Q250時間：按程序運行的系統(tǒng)時鐘時間，單位秒.2/7/202312輸出文件格式定義：銀行銀行運行結(jié)果記錄文件格式：文本文件，每一行表示一個營業(yè)廳窗口的叫號、暫停休息、準備下班、進入空閑、下班等動作，各窗口狀態(tài)和正在服務(wù)的客戶號碼，以及等待服務(wù)的客戶情況。格式定義如下： T=<當(dāng)前時間>,Event=<事件描述>,Now=<各窗口狀態(tài)>,Wait=<等待服務(wù)的客戶情況><\n>

<事件描述>=JH<空格><W窗口號><空格><C客戶號碼> ZT><空格><W窗口號><空格><R休息時長> KX><空格><W窗口號>ZB><空格><下班時間>XB 2/7/202313輸出文件格式定義：銀行 <客戶號碼>=0001~9999<各窗口狀態(tài)>=<W窗口號><空格><S窗口狀態(tài)><空格><C當(dāng)前客戶號碼> <S窗口狀態(tài)>=S0表示空閑 S1表示服務(wù) S2表示暫停<等待服務(wù)的客戶情況>=

策略1：<Q隊列長度>><空格><F隊首客戶號碼><空格><L隊尾客戶號碼>

策略2：<W窗口號>><空格><隊列中客戶號碼>例:T=3,Event=JHW2C0009,Now=W1S1

C0004W2S2C0000W3S0C0000,Wait=Q19F0010L002814用有限狀態(tài)自動機模型實現(xiàn)復(fù)雜的過程控制策略15什么是有限狀態(tài)自動機？FiniteStateMachine,又稱有限狀態(tài)機或簡稱狀態(tài)機，是表示有限個狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動作等行為的數(shù)學(xué)模型。狀態(tài)：存儲關(guān)于過去的信息，就是說,它反映從系統(tǒng)開始到現(xiàn)在時刻的輸入變化。轉(zhuǎn)移:指示狀態(tài)變更，并且用必須滿足來確使轉(zhuǎn)移發(fā)生的條件來描述它。動作:是在給定時刻要進行的活動的描述。有多種類型的動作：進入動作（Entryaction）-在進入狀態(tài)時進行退出動作-在退出狀態(tài)時進行輸入動作-依賴于當(dāng)前狀態(tài)和輸入條件進行轉(zhuǎn)移動作-在進行特定轉(zhuǎn)移時進行16為了描述一個有限狀態(tài)機的工作狀況，可采用狀態(tài)轉(zhuǎn)換圖。狀態(tài)轉(zhuǎn)換圖是一個有向圖，圖中的每個節(jié)點表示一種狀態(tài)，一條邊（或弧）表示一個轉(zhuǎn)換關(guān)系。初始狀態(tài)通常用“沒有起點的箭頭”指向它來表示。終止?fàn)顟B(tài)是機器完成了它的程序之后的狀態(tài)，它通常表示為雙重圓圈。q0q1q3q2aabbb狀態(tài)轉(zhuǎn)換圖a17狀態(tài)表除了狀態(tài)轉(zhuǎn)換圖以外,還可以使用多種類型的狀態(tài)轉(zhuǎn)移表。最常見的表示如下：當(dāng)前狀態(tài)和條件的組合指示出下一個狀態(tài)。完整的動作信息可以只使用腳注來增加。狀態(tài)轉(zhuǎn)移表當(dāng)前狀態(tài)→

條件↓狀態(tài)A狀態(tài)B狀態(tài)C條件X………條件Y…狀態(tài)C…條件Z………18FSM有兩個不同的類別：接受器／識別器和變換器。接受器產(chǎn)生一個二元輸出，說要么“是”要么“否”來回答輸入是否被機器接受。在所有輸入都被處理了的時候，如果當(dāng)前狀態(tài)是接受狀態(tài)，輸入被接受；否則被拒絕。作為規(guī)則，輸入是符號（字符）；動作不使用。接受器狀態(tài)機q0q1q3q2aabbbErr非a或ba19變換器使用動作基于給定輸入和／或狀態(tài)生成輸出。常分為兩種類型：Moore機和Mealy機。Moore機-只使用進入動作的FSM，就是說輸出只依賴于狀態(tài)。Moore模型的好處是行為的簡單性。例：一個電梯門的MooreFSM。狀態(tài)“Opening”中的進入動作(E:)開啟電機開門，在狀態(tài)“Closing”中的進入動作以反方向開啟電機關(guān)門。狀態(tài)“Opened”和“Closed”不進行任何動作。變換器狀態(tài)機（1）q0openingcmd_opencmd_closecloseing開門關(guān)門openedclosed20Mealy機-只使用輸入動作的FSM，就是說輸出依賴于輸入和狀態(tài)。MealyFSM的使用經(jīng)常導(dǎo)致狀態(tài)數(shù)目的簡約。例：電梯門的MealyFSM有兩個輸入動作：“開啟電機關(guān)門如果command_close下達”和“反向開啟電機開門如果

command_open下達”。變換器狀態(tài)機（2）q0openedcmd_open/開門cmd_close/關(guān)門closed21FSM的類型在實踐中經(jīng)常使用混合模型。進一步可區(qū)分為確定型（DFA）和非確定型（NDFA、GNFA）自動機。在確定型自動機中，每個狀態(tài)對每個可能輸入只有精確的一個轉(zhuǎn)移。在非確定型自動機中，給定狀態(tài)對給定可能輸入可以沒有或有多于一個轉(zhuǎn)移。這個區(qū)分在實踐而非理論中更有用，因為存在算法把任何NDFA轉(zhuǎn)換成等價的DFA，盡管這種轉(zhuǎn)換一般會增加自動機的復(fù)雜性。22有限狀態(tài)自動機的應(yīng)用有限狀態(tài)自動機在很多不同領(lǐng)域中都是重要的，包括電子工程、語言學(xué)、計算機科學(xué)、哲學(xué)、生物學(xué)、數(shù)學(xué)和邏輯學(xué)。有限狀態(tài)機是在自動機理論和計算理論中研究的一類自動機。在計算機科學(xué)中，有限狀態(tài)機被廣泛用于建模應(yīng)用行為、硬件電路系統(tǒng)設(shè)計、軟件工程，編譯器、網(wǎng)絡(luò)協(xié)議、和計算與語言的研究。針對許多類型的編程問題，建立有限狀態(tài)自動機模型，可以為分析、求解帶來很大的幫助。23例1：串口通信 兩臺微機通過串口通信,需在兩臺機器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動機，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開連接發(fā)出連接請求q0q1q2q0：空閑狀態(tài)q1:等待應(yīng)答狀態(tài)q2：通信狀態(tài)24例2：打電話(狀態(tài)機在通信領(lǐng)域的應(yīng)用)。 在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機，撥號，應(yīng)答，進行通話等過程，話機的狀態(tài)及狀態(tài)遷移如下所示。q0q1q2q3q4摘機收到撥號音撥號收應(yīng)答信號掛機收齊號碼q0:空閑狀態(tài)q1:等待撥號音狀態(tài)q2:可以撥號狀態(tài)q3:等待應(yīng)答狀態(tài)q4:通話狀態(tài)狀態(tài)遷移狀態(tài)25

接受器有限狀態(tài)機的形式化定義一個五元組其中：：有限的狀態(tài)集合；：有限的輸入字母表；：轉(zhuǎn)換函數(shù)，是到的映射；：初始狀態(tài)，；

：

終止?fàn)顟B(tài)集，

；接受器的形式化定義（初始狀態(tài)只有一個）26aq0q1q3q2aabbb狀態(tài)集合字母表初始狀態(tài)終止?fàn)顟B(tài)集轉(zhuǎn)換函數(shù)例3:用于識別輸入的字符串是否是或者形式的有限自動機。27程序設(shè)計實例研究應(yīng)用有限狀態(tài)機模型求解問題，關(guān)鍵就是抽象出狀態(tài)，描述出狀態(tài)轉(zhuǎn)移圖和狀態(tài)轉(zhuǎn)移函數(shù)應(yīng)用有限狀態(tài)機解題步驟1、確定輸入集2、繪制狀態(tài)遷移圖（確定狀態(tài)，在每一個狀態(tài)下對輸入進行分類，確定下一個狀態(tài)）3、確定狀態(tài)轉(zhuǎn)移函數(shù)（在某狀態(tài)下，接收到某一字符后，自動機要執(zhí)行的操作，以及遷移到的下一狀態(tài)）28程序設(shè)計實例研究例4檢驗輸入是否是合法的C語言注釋/*…*/導(dǎo)論教材P172,圖10.10,注意讀程序?qū)嵗齫1:等待*狀態(tài)q2：注釋開始狀態(tài)q3:等待/以結(jié)束注釋狀態(tài)q4：已接收注釋結(jié)束狀態(tài)29程序設(shè)計實例研究轉(zhuǎn)換函數(shù)分析start狀態(tài)下：輸入‘/’:state=q1輸出非‘/’:state=ERRORq1狀態(tài)下：輸入‘*’:state=q2輸出非‘*’:state=ERRORq2狀態(tài)下：輸入‘*’:state=q3輸入EOF：state=ERROR輸出其他:state=q2306.2程序設(shè)計實例研究轉(zhuǎn)換函數(shù)分析(續(xù)）q3狀態(tài)下：輸入‘*’:狀態(tài)不變輸入‘/’:state=q4輸入EOF：state=ERROR輸出其他:state=q2q4狀態(tài)下：輸入EOF：state=ACCEPT輸出其他:state=ERROR316.2程序設(shè)計實例研究例5去除C語言注釋32有限狀態(tài)機解題通用處理模式有限狀態(tài)機解題通用處理模式#defineSTART1...intstate=START;...while(state!=END){ ch=getch();switch(state){ caseSTART: if(ch==?)state=Q1;break;...}33為什么要用狀態(tài)機?有限狀態(tài)機到底有什么好處？怎樣才算應(yīng)用狀態(tài)機解題？1、狀態(tài)機用數(shù)學(xué)模型來設(shè)計解題思路，準確可靠、簡練，而程序員僅僅依靠自己的腦力和復(fù)雜的程序結(jié)構(gòu)。2、狀態(tài)機模型的思路和人解決問題的思路是一致的，都是把復(fù)雜的問題逐步分解為簡單的步驟。所以狀態(tài)機模型是程序員的好助手，不是你的競爭對手。3、狀態(tài)機解題的特征：在連續(xù)輸入的邏輯判斷過程中，有清楚的狀態(tài)分段，各狀態(tài)段之間的邏輯跳轉(zhuǎn)有嚴謹?shù)倪w移規(guī)則。4、應(yīng)用狀態(tài)機設(shè)計的程序最終表現(xiàn)出的清晰嚴謹?shù)倪壿嫿Y(jié)構(gòu)，而不是可讀性很差的“聰明”代碼。34例6:輸入一個字符串，以’#’結(jié)束，要求判斷其是否滿足anbncn形式。程序