有限状态机应用

1大作业-文件IO版本设计思路2/7/20232大作业文件IO版本模块结构图模型内部状态控制器策略算法结果记录写入文件状态变化事件改变状态文件输入读取请求事件时间同步2/7/20233大作业文件IO版本程序框架/*大作业文件IO版本的程序主体结构*/structSTATE{…}//电梯或银行的运行状态structLIST{…}//请求队列链表节点structREQ{…}//暂存每次获得的请求事件intmain(){inttimeCount=0;//计时器，每循环一次模拟2msstructREQtheReq={};//暂存每次获得的请求事件structSTATEpreST,theST={}; //保存电梯或银行的运行状态structLIST*headp=NULL;//存请求队列链表头指针File*fpin,*fpout;2/7/20234大作业文件IO版本程序框架openFile(**fpin,**fpout);//打开输入输出文件theReq=get_fileInput(fpin);//读取第一个请求while(!(endInput(fpin)&&isIdle(theST))){ //当文件输入结束，且电梯或营业厅空闲才退出 if(theReq.time==timeCount){

headp=addServList(headp,theReq,theST,1); /*当请求事件发生的时间到，添加请求事件到服务队列中,策略参数为1对应先来先服务，2对应顺便服务*/ theReq=get_fileInput(fpin); //读取文件中的下一个请求事件 }//endif

2/7/20235大作业文件IO版本程序框架

preST=theST; theST=runService(preST,&headp,timeCount);

if(theST.state!=preST.state) set_fileOutput(fpout,timeCount,theST, headp); /*当状态变化，将当前时间、状态和等待队列的情况写入到文件中。*/ timeCount++; }//endwhile closeFile(fpin,fpout);//关闭输入输出文件 return0;}//endmain2/7/20236大作业文件IO版本函数接口intendInput(File*fp)//判断文件输入是否结束intisIdle(structSTATEstate)//判断电梯或营业厅当前状态是否空闲structREQget_fileInput(File*fp)//顺序读取文件中的一个请求事件structLIST*addServList(structLIST*hp,structREQreq,structSTATEstate,intmode);//按照策略，将新请求插入请求队列中structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根据状态、请求和时间条件，运行电梯或营业厅服务。运行服务后将改变的状态返回。注意当服务完一个请求后，删除该节点并修改头指针！*/2/7/20237大作业文件IO版本函数接口structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根据状态、请求和时间条件，运行电梯或营业厅服务。运行服务后将改变的状态返回。注意当服务完一个请求后，删除该节点并修改头指针！*/voidset_fileOutput(File*fp,inttime,structSTATEstate,structLIST*hp)/*将当前时间、状态和等待队列的情况顺序写入文件*/2/7/20238输入文件格式定义：电梯输入用电梯请求文件格式：文本文件，每一行表示一个时刻发生的电梯请求。格式定义如下： T=<请求发生时间>,CallF=<楼层请求><\n>例:T=1,CallF=4UT=2,CallF=4U5T请求发生时间：按程序运行的系统时钟时间，单位秒.楼层请求：由呼叫方向(U/D/T)和数字（1～9）组成，同时有多个请求时用空格分割。如2U5D6T，表示2层上行呼叫、5层下行呼叫、6层目标停靠。2/7/20239输出文件格式定义：电梯电梯运行结果记录文件格式：文本文件，每一行表示一个电梯停靠或启动、转向动作，当前楼层和目标楼层，以及排队的楼层请求。格式定义如下： T=<当前时间>,State=<电梯状态>,NowF=<电梯当前楼层>,GoalF=<电梯目标楼层>,StopT=<停靠时间>,WaitF=<未响应的楼层请求><\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输出文件格式定义：电梯当前时间：程序开始运行的系统时钟时间，单位秒。电梯状态：UP_RUN表示向上运行、DOWN_RUN表示向下运行、UP_STOP表示上行停靠、DOWN_STOP表示下行停靠、IDLE表示空闲。电梯当前楼层：1.0-9.0。停靠时间：记录电梯已经停靠的时间,单位秒。只有在停靠状态下，该信息才大于0。未响应的楼层请求：按照电梯控制策略，按响应顺序将尚未响应的呼叫请求和目标楼层列出来。是由呼叫方向(U/D/T)和数字（1～9）组成的序列，中间用一个空格分割。如2U5D6T，表示2层上行呼叫、5层下行呼叫、6层目标停靠。2/7/202311输入文件格式定义：银行输入用银行请求文件格式：文本文件，每一行表示一个时刻发生的客户到达事件、窗口休息请求或下班指令。格式定义如下： T=<请求发生时间>,Req=<请求><\n> <请求>=C<客户人数>|W<请求休息的窗口号> |Q<下班时间>例:T=1,Req=C5T=6,Req=W3T=200,Req=Q250时间：按程序运行的系统时钟时间，单位秒.2/7/202312输出文件格式定义：银行银行运行结果记录文件格式：文本文件，每一行表示一个营业厅窗口的叫号、暂停休息、准备下班、进入空闲、下班等动作，各窗口状态和正在服务的客户号码，以及等待服务的客户情况。格式定义如下： T=<当前时间>,Event=<事件描述>,Now=<各窗口状态>,Wait=<等待服务的客户情况><\n>

<事件描述>=JH<空格><W窗口号><空格><C客户号码> ZT><空格><W窗口号><空格><R休息时长> KX><空格><W窗口号>ZB><空格><下班时间>XB 2/7/202313输出文件格式定义：银行 <客户号码>=0001~9999<各窗口状态>=<W窗口号><空格><S窗口状态><空格><C当前客户号码> <S窗口状态>=S0表示空闲 S1表示服务 S2表示暂停<等待服务的客户情况>=

策略1：<Q队列长度>><空格><F队首客户号码><空格><L队尾客户号码>

策略2：<W窗口号>><空格><队列中客户号码>例:T=3,Event=JHW2C0009,Now=W1S1

C0004W2S2C0000W3S0C0000,Wait=Q19F0010L002814用有限状态自动机模型实现复杂的过程控制策略15什么是有限状态自动机？FiniteStateMachine,又称有限状态机或简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。状态：存储关于过去的信息，就是说,它反映从系统开始到现在时刻的输入变化。转移:指示状态变更，并且用必须满足来确使转移发生的条件来描述它。动作:是在给定时刻要进行的活动的描述。有多种类型的动作：进入动作（Entryaction）-在进入状态时进行退出动作-在退出状态时进行输入动作-依赖于当前状态和输入条件进行转移动作-在进行特定转移时进行16为了描述一个有限状态机的工作状况，可采用状态转换图。状态转换图是一个有向图，图中的每个节点表示一种状态，一条边（或弧）表示一个转换关系。初始状态通常用“没有起点的箭头”指向它来表示。终止状态是机器完成了它的程序之后的状态，它通常表示为双重圆圈。q0q1q3q2aabbb状态转换图a17状态表除了状态转换图以外,还可以使用多种类型的状态转移表。最常见的表示如下：当前状态和条件的组合指示出下一个状态。完整的动作信息可以只使用脚注来增加。状态转移表当前状态→

条件↓状态A状态B状态C条件X………条件Y…状态C…条件Z………18FSM有两个不同的类别：接受器／识别器和变换器。接受器产生一个二元输出，说要么“是”要么“否”来回答输入是否被机器接受。在所有输入都被处理了的时候，如果当前状态是接受状态，输入被接受；否则被拒绝。作为规则，输入是符号（字符）；动作不使用。接受器状态机q0q1q3q2aabbbErr非a或ba19变换器使用动作基于给定输入和／或状态生成输出。常分为两种类型：Moore机和Mealy机。Moore机-只使用进入动作的FSM，就是说输出只依赖于状态。Moore模型的好处是行为的简单性。例：一个电梯门的MooreFSM。状态“Opening”中的进入动作(E:)开启电机开门，在状态“Closing”中的进入动作以反方向开启电机关门。状态“Opened”和“Closed”不进行任何动作。变换器状态机（1）q0openingcmd_opencmd_closecloseing开门关门openedclosed20Mealy机-只使用输入动作的FSM，就是说输出依赖于输入和状态。MealyFSM的使用经常导致状态数目的简约。例：电梯门的MealyFSM有两个输入动作：“开启电机关门如果command_close下达”和“反向开启电机开门如果

command_open下达”。变换器状态机（2）q0openedcmd_open/开门cmd_close/关门closed21FSM的类型在实践中经常使用混合模型。进一步可区分为确定型（DFA）和非确定型（NDFA、GNFA）自动机。在确定型自动机中，每个状态对每个可能输入只有精确的一个转移。在非确定型自动机中，给定状态对给定可能输入可以没有或有多于一个转移。这个区分在实践而非理论中更有用，因为存在算法把任何NDFA转换成等价的DFA，尽管这种转换一般会增加自动机的复杂性。22有限状态自动机的应用有限状态自动机在很多不同领域中都是重要的，包括电子工程、语言学、计算机科学、哲学、生物学、数学和逻辑学。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。针对许多类型的编程问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。23例1：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接发出连接请求q0q1q2q0：空闲状态q1:等待应答状态q2：通信状态24例2：打电话(状态机在通信领域的应用)。 在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。q0q1q2q3q4摘机收到拨号音拨号收应答信号挂机收齐号码q0:空闲状态q1:等待拨号音状态q2:可以拨号状态q3:等待应答状态q4:通话状态状态迁移状态25

接受器有限状态机的形式化定义一个五元组其中：：有限的状态集合；：有限的输入字母表；：转换函数，是到的映射；：初始状态，；

：

终止状态集，

；接受器的形式化定义（初始状态只有一个）26aq0q1q3q2aabbb状态集合字母表初始状态终止状态集转换函数例3:用于识别输入的字符串是否是或者形式的有限自动机。27程序设计实例研究应用有限状态机模型求解问题，关键就是抽象出状态，描述出状态转移图和状态转移函数应用有限状态机解题步骤1、确定输入集2、绘制状态迁移图（确定状态，在每一个状态下对输入进行分类，确定下一个状态）3、确定状态转移函数（在某状态下，接收到某一字符后，自动机要执行的操作，以及迁移到的下一状态）28程序设计实例研究例4检验输入是否是合法的C语言注释/*…*/导论教材P172,图10.10,注意读程序实例q1:等待*状态q2：注释开始状态q3:等待/以结束注释状态q4：已接收注释结束状态29程序设计实例研究转换函数分析start状态下：输入‘/’:state=q1输出非‘/’:state=ERRORq1状态下：输入‘*’:state=q2输出非‘*’:state=ERRORq2状态下：输入‘*’:state=q3输入EOF：state=ERROR输出其他:state=q2306.2程序设计实例研究转换函数分析(续）q3状态下：输入‘*’:状态不变输入‘/’:state=q4输入EOF：state=ERROR输出其他:state=q2q4状态下：输入EOF：state=ACCEPT输出其他:state=ERROR316.2程序设计实例研究例5去除C语言注释32有限状态机解题通用处理模式有限状态机解题通用处理模式#defineSTART1...intstate=START;...while(state!=END){ ch=getch();switch(state){ caseSTART: if(ch==?)state=Q1;break;...}33为什么要用状态机?有限状态机到底有什么好处？怎样才算应用状态机解题？1、状态机用数学模型来设计解题思路，准确可靠、简练，而程序员仅仅依靠自己的脑力和复杂的程序结构。2、状态机模型的思路和人解决问题的思路是一致的，都是把复杂的问题逐步分解为简单的步骤。所以状态机模型是程序员的好助手，不是你的竞争对手。3、状态机解题的特征：在连续输入的逻辑判断过程中，有清楚的状态分段，各状态段之间的逻辑跳转有严谨的迁移规则。4、应用状态机设计的程序最终表现出的清晰严谨的逻辑结构，而不是可读性很差的“聪明”代码。34例6:输入一个字符串，以’#’结束，要求判断其是否满足anbncn形式。程序