有限状态机应用

1、1,大作业-文件IO版本 设计思路,8/10/2020,2,大作业文件IO版本模块结构图,8/10/2020,3,大作业文件IO版本程序框架,/* 大作业文件IO版本的程序主体结构 */ struct STATE /电梯或银行的运行状态 struct LIST /请求队列链表节点 struct REQ /暂存每次获得的请求事件 int main() int timeCount=0; /计时器，每循环一次模拟2ms struct REQ theReq=; /暂存每次获得的请求事件 struct STATE preST,theST =; /保存电梯或银行的运行状态 struct LIST *hea

2、dp=NULL;/存请求队列链表头指针 File *fpin,*fpout;,8/10/2020,4,大作业文件IO版本程序框架,openFile(*fpin,*fpout); /打开输入输出文件 theReq=get_fileInput(fpin); /读取第一个请求 while (!(endInput(fpin) /读取文件中的下一个请求事件 /end if,8/10/2020,5,大作业文件IO版本程序框架,preST=theST; theST=runService(preST, /end main,8/10/2020,6,大作业文件IO版本函数接口,int endInput(File

3、*fp)/判断文件输入是否结束 int isIdle(struct STATE state) /判断电梯或营业厅当前状态是否空闲 struct REQ get_fileInput(File *fp) /顺序读取文件中的一个请求事件 struct LIST * addServList(struct LIST *hp,struct REQ req, struct STATE state, int mode); /按照策略，将新请求插入请求队列中 struct STATE runService(struct STATE state, struct LIST *hp,int time) /*根据状态、

4、请求和时间条件，运行电梯或营业厅服务。 运行服务后将改变的状态返回。注意当服务完一个请求后，删除该节点并修改头指针！*/,8/10/2020,7,大作业文件IO版本函数接口,struct STATE runService(struct STATE state, struct LIST *hp,int time) /*根据状态、请求和时间条件，运行电梯或营业厅服务。 运行服务后将改变的状态返回。注意当服务完一个请求后，删除该节点并修改头指针！*/ void set_fileOutput(File *fp,int time,struct STATE state, struct LIST *hp)

5、/*将当前时间、状态和等待队列的情况顺序写入文件*/,8/10/2020,8,输入文件格式定义：电梯,输入用电梯请求文件格式： 文本文件，每一行表示一个时刻发生的电梯请求。格式定义如下： T=,CallF= 例:T=1,CallF=4U T=2,CallF=4U 5T 请求发生时间：按程序运行的系统时钟时间，单位秒. 楼层请求：由呼叫方向(U/D/T)和数字（19）组成，同时有多个请求时用空格分割。如2U 5D 6T，表示2层上行呼叫、5层下行呼叫、6层目标停靠。,8/10/2020,9,输出文件格式定义：电梯,电梯运行结果记录文件格式： 文本文件，每一行表示一个电梯停靠或启动、转向动作，当前

6、楼层和目标楼层，以及排队的楼层请求。格式定义如下： T=,State=,NowF=,GoalF=,StopT=, WaitF= 例:T=3,State=UP_RUN,NowF=1.0,GoalF=3, StopT=0,WaitF=4U 5D 6T T=3,State=UP,NowF=1.0,GoalF=3,StopT=0, WaitF=4U 5T 6U 9D 8D,8/10/2020,10,输出文件格式定义：电梯,当前时间：程序开始运行的系统时钟时间，单位秒。 电梯状态：UP_RUN表示向上运行、DOWN_RUN表示向下运行、UP_STOP表示上行停靠、DOWN_STOP表示下行停靠、IDLE

7、表示空闲。 电梯当前楼层：1.0-9.0。停靠时间：记录电梯已经停靠的时间,单位秒。只有在停靠状态下，该信息才大于0。 未响应的楼层请求：按照电梯控制策略，按响应顺序将尚未响应的呼叫请求和目标楼层列出来。是由呼叫方向(U/D/T)和数字（19）组成的序列，中间用一个空格分割。如2U 5D 6T，表示2层上行呼叫、5层下行呼叫、6层目标停靠。,8/10/2020,11,输入文件格式定义：银行,输入用银行请求文件格式： 文本文件，每一行表示一个时刻发生的客户到达事件、窗口休息请求或下班指令。格式定义如下： T=,Req= =C | W | Q 例:T=1,Req=C5 T=6,Req=W3 T=2

8、00,Req=Q250 时间：按程序运行的系统时钟时间，单位秒.,8/10/2020,12,输出文件格式定义：银行,银行运行结果记录文件格式： 文本文件，每一行表示一个营业厅窗口的叫号、暂停休息、准备下班、进入空闲、下班等动作，各窗口状态和正在服务的客户号码，以及等待服务的客户情况。格式定义如下： T=,Event=,Now=, Wait= =JH ZT KX ZB XB,8/10/2020,13,输出文件格式定义：银行,=00019999 = = S0 表示空闲 S1 表示服务 S2 表示暂停 = 策略1： 策略2： 例:T=3,Event=JH W2 C0009,Now=W1 S1 C00

9、04 W2 S2 C0000 W3 S0 C0000,Wait=Q19 F0010 L0028,14,15,什么是有限状态自动机？,Finite State Machine,又称有限状态机或简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。 状态：存储关于过去的信息，就是说,它反映从系统开始到现在时刻的输入变化。 转移:指示状态变更，并且用必须满足来确使转移发生的条件来描述它。 动作:是在给定时刻要进行的活动的描述。有多种类型的动作： 进入动作（Entry action）-在进入状态时进行 退出动作 -在退出状态时进行 输入动作 -依赖于当前状态和输入条件进行 转移动

10、作 -在进行特定转移时进行,16,为了描述一个有限状态机的工作状况，可采用状态转换图。状态转换图是一个有向图，图中的每个节点表示一种状态，一条边（或弧）表示一个转换关系。 初始状态通常用 “没有起点的箭头” 指向它来表示。 终止状态是机器 完成了它的程序之后 的状态，它通常表示 为双重圆圈。,状态转换图,a,17,状态表,除了状态转换图以外,还可以使用多种类型的状态转移表。最常见的表示如下： 当前状态和条件的组合指示出下一个状态。 完整的动作信息可以只使用脚注来增加。,18,FSM有两个不同的类别：接受器识别器和变换器。 接受器产生一个二元输出，说要么“是”要么“否”来回答输入是否被机器接受。

11、 在所有输入都被处理了的时候， 如果当前状态是接受状态，输入被接受； 否则被拒绝。 作为规则，输入是符号 （字符）；动作不使用。,接受器状态机,Err,非a或b,a,19,变换器使用动作基于给定输入和或状态生成输出。常分为两种类型：Moore机和Mealy机。 Moore机-只使用进入动作的FSM，就是说输出只依赖于状态。Moore 模型的好处是行为的简单性。 例：一个电梯门的 Moore FSM。 状态“Opening”中的进入 动作 (E:) 开启电机开门， 在状态“Closing”中的进入 动作以反方向开启电机关门。 状态“Opened”和“Closed” 不进行任何动作。,变换器状态机

12、（1）,q0,opening,cmd_open,cmd_close,closeing,开门,关门,opened,closed,20,Mealy机-只使用输入动作的FSM，就是说输出依赖于输入和状态。 Mealy FSM 的使用经常导致状态数目的简约。 例：电梯门的Mealy FSM 有两个输入动作：“开启电机 关门如果 command_close 下达” 和“反向开启电机开门如果 command_open 下达”。,变换器状态机（2）,q0,opened,cmd_open/开门,cmd_close/关门,closed,21,FSM的类型,在实践中经常使用混合模型。 进一步可区分为确定型（DFA

13、）和非确定型（NDFA、GNFA）自动机。在确定型自动机中，每个状态对每个可能输入只有精确的一个转移。在非确定型自动机中，给定状态对给定可能输入可以没有或有多于一个转移。 这个区分在实践而非理论中更有用，因为存在算法把任何 NDFA 转换成等价的 DFA，尽管这种转换一般会增加自动机的复杂性。,22,有限状态自动机的应用,有限状态自动机在很多不同领域中都是重要的，包括电子工程、 语言学、计算机科学、哲学、生物学、数学和逻辑学。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。

14、 针对许多类型的编程问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。,23,例1：串口通信 两台微机通过串口通信, 需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。,q0：空闲状态 q1: 等待应答状态 q2：通信状态,24,例2：打电话 (状态机在通信领域的应用)。 在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。,状态迁移,状态,25,接受器有限状态机的形式化定义 一个五元组 其中： ：有限的状态集合； ：有限的输入字母表； ： 转换函数，是 到 的映射； ： 初始状态， ； ：

15、 终止状态集， ；,接受器的形式化定义,（初始状态只有一个）,26,a,转换函数,例3:用于识别输入的字符串是否是 或者 形式的有限自动机。,27,程序设计实例研究,应用有限状态机模型求解问题，关键就是抽象出状态，描述出状态转移图和状态转移函数 应用有限状态机解题步骤 1、确定输入集 2、绘制状态迁移图（确定状态，在每一个状态下对输入进行分类，确定下一个状态） 3、确定状态转移函数（在某状态下，接收到某一字符后，自动机要执行的操作，以及迁移到的下一状态）,28,程序设计实例研究,例4 检验输入是否是合法的C语言注释/*/ 导论教材P172,图10.10,注意读程序实例,q1:等待*状态 q2：

16、注释开始状态 q3: 等待/以结束注释状态 q4：已接收注释结束状态,29,程序设计实例研究,转换函数分析 start状态下： 输入/:state=q1 输出非/:state=ERROR q1状态下： 输入*:state=q2 输出非*:state=ERROR q2状态下： 输入*:state=q3 输入EOF：state=ERROR 输出其他: state=q2,30,6.2 程序设计实例研究,转换函数分析(续） q3状态下： 输入*:状态不变 输入/:state=q4 输入EOF：state=ERROR 输出其他: state=q2 q4状态下： 输入EOF：state=ACCEPT 输出

17、其他: state=ERROR,31,6.2 程序设计实例研究,例5 去除C语言注释,32,有限状态机解题通用处理模式,有限状态机解题通用处理模式,#define START 1 . int state=START; . while (state!=END) ch=getch(); switch(state) case START: if (ch=?) state=Q1; break; .,33,为什么要用状态机?,有限状态机到底有什么好处？怎样才算应用状态机解题？ 1、状态机用数学模型来设计解题思路，准确可靠、简练，而程序员仅仅依靠自己的脑力和复杂的程序结构。 2、状态机模型的思路和人解决问

18、题的思路是一致的，都是把复杂的问题逐步分解为简单的步骤。所以状态机模型是程序员的好助手，不是你的竞争对手。 3、状态机解题的特征：在连续输入的逻辑判断过程中，有清楚的状态分段，各状态段之间的逻辑跳转有严谨的迁移规则。 4、应用状态机设计的程序最终表现出的清晰严谨的逻辑结构，而不是可读性很差的“聪明”代码。,34,例6: 输入一个字符串，以#结束，要求判断其是否满足anbncn形式。 程序运行效果如下： 例1： Please input string consist of a/b/c, #to end: aabbcc# the string is acceptable 例2： Please input string consist of a/b/c,#to end: aabbc# the string