有限状态机应用

1、 1 大作业大作业-文件文件IO版本版本 设计思路设计思路 7/12/2021 2 大作业文件IO版本模块结构图 模型模型 内部状态 控制器控制器 策略算法 结果记录结果记录 写入文件 状态 变化 事件 改变 状态 文件输入文件输入 读取请求 事件 时间同步时间同步 7/12/2021 3 大作业文件IO版本程序框架 /* 大作业文件大作业文件IO版本的程序主体结构版本的程序主体结构 */ struct STATE /电梯或银行的运行状态电梯或银行的运行状态 struct LIST /请求队列链表节点请求队列链表节点 struct REQ /暂存每次获得的请求事件暂存每次获得的请求事件 int

2、 main() int timeCount=0; /计时器，每循环一次模拟计时器，每循环一次模拟2ms struct REQ theReq=; /暂存每次获得的请求事件暂存每次获得的请求事件 struct STATE preST,theST =; /保存电梯或银行的运行状态保存电梯或银行的运行状态 struct LIST *headp=NULL;/存请求队列链表头指针存请求队列链表头指针 File *fpin,*fpout; 7/12/2021 4 大作业文件IO版本程序框架 openFile(*fpin,*fpout); /打开输入输出文件打开输入输出文件 theReq=get_fileIn

3、put(fpin); /读取第一个请求读取第一个请求 while (!(endInput(fpin) /*当请求事件发生的时间到，添加请求事件到服当请求事件发生的时间到，添加请求事件到服 务队列中务队列中, 策略参数为策略参数为1对应先来先服务，对应先来先服务，2对应顺便对应顺便 服务服务*/ theReq=get_fileInput(fpin); /读取文件中的下一个请求事件读取文件中的下一个请求事件 /end if 7/12/2021 5 大作业文件IO版本程序框架 preST=theST; theST=runService(preST, if (theST.state!=preST.st

4、ate) set_fileOutput(fpout,timeCount,theST, headp); /*当状态变化，将当前时间、状态和等待队列当状态变化，将当前时间、状态和等待队列 的情况写入到文件中。的情况写入到文件中。 */ timeCount+; /end while closeFile(fpin,fpout); /关闭输入输出文件关闭输入输出文件 return 0; /end main 7/12/2021 6 大作业文件IO版本函数接口 int endInput(File *fp)/判断文件输入是否结束判断文件输入是否结束 int isIdle(struct STATE state)

5、 /判断电梯或营业厅当前状态是否空闲判断电梯或营业厅当前状态是否空闲 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) /*根据状态、

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

7、意当服务完一个请求注意当服务完一个请求 后，删除该节点并修改头指针！后，删除该节点并修改头指针！*/ void set_fileOutput(File *fp,int time,struct STATE state, struct LIST *hp) /*将当前时间、状态和等待队列的情况顺序写入文件将当前时间、状态和等待队列的情况顺序写入文件*/ 7/12/2021 8 输入文件格式定义：电梯输入文件格式定义：电梯 输入用电梯请求文件格式：输入用电梯请求文件格式： 文本文件，每一行表示一个时刻发生的电梯请求。文本文件，每一行表示一个时刻发生的电梯请求。 格式定义如下：格式定义如下： T=,Ca

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

9、向文本文件，每一行表示一个电梯停靠或启动、转向 动作，当前楼层和目标楼层，以及排队的楼层请求。动作，当前楼层和目标楼层，以及排队的楼层请求。 格式定义如下：格式定义如下： 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 7/12/2021 10 输出文件格式定义：电梯输出文件格式定义：电梯 当前时间：程序开始运行的系统时钟时间，

10、单位秒。当前时间：程序开始运行的系统时钟时间，单位秒。 电梯状态：电梯状态：UP_RUN表示向上运行、表示向上运行、DOWN_RUN 表示向下运行、表示向下运行、UP_STOP表示上行停靠、表示上行停靠、 DOWN_STOP表示下行停靠、表示下行停靠、IDLE表示空闲。表示空闲。 电梯当前楼层：电梯当前楼层：1.0-9.0。停靠时间：记录电梯已经。停靠时间：记录电梯已经 停靠的时间停靠的时间,单位秒。只有在停靠状态下，该信息单位秒。只有在停靠状态下，该信息 才大于才大于0。 未响应的楼层请求：按照电梯控制策略，按响应顺未响应的楼层请求：按照电梯控制策略，按响应顺 序将尚未响应的呼叫请求和目标楼

11、层列出来。是由序将尚未响应的呼叫请求和目标楼层列出来。是由 呼叫方向呼叫方向(U/D/T)和数字（和数字（19）组成的序列，中）组成的序列，中 间用一个空格分割。如间用一个空格分割。如2U 5D 6T，表示，表示2层上行呼层上行呼 叫、叫、5层下行呼叫、层下行呼叫、6层目标停靠。层目标停靠。 7/12/2021 11 输入文件格式定义：银行输入文件格式定义：银行 输入用银行请求文件格式：输入用银行请求文件格式： 文本文件，每一行表示一个时刻发生的客户到达事文本文件，每一行表示一个时刻发生的客户到达事 件、窗口休息请求或下班指令。格式定义如下：件、窗口休息请求或下班指令。格式定义如下： T=,R

12、eq= =C | W | Q 例例:T=1,Req=C5 T=6,Req=W3 T=200,Req=Q250 时间：按程序运行的系统时钟时间，单位秒时间：按程序运行的系统时钟时间，单位秒. 7/12/2021 12 输出文件格式定义：银行输出文件格式定义：银行 银行运行结果记录文件格式：银行运行结果记录文件格式： 文本文件，每一行表示一个营业厅窗口的叫号、暂停休息、文本文件，每一行表示一个营业厅窗口的叫号、暂停休息、 准备下班、进入空闲、下班等动作，各窗口状态和正在服准备下班、进入空闲、下班等动作，各窗口状态和正在服 务的客户号码，以及等待服务的客户情况。格式定义如下：务的客户号码，以及等待服

13、务的客户情况。格式定义如下： T=,Event=,Now=, Wait= =JH ZT KX ZB XB 7/12/2021 13 输出文件格式定义：银行输出文件格式定义：银行 =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 用有限状态自动机模型用有限状态自动机模型 实现复杂的过程控制策略实现复杂的过程控制策略 15 什么是有限状态自动

14、机？什么是有限状态自动机？ Finite State Machine,Finite State Machine,又称有限状态机或简称状态机，又称有限状态机或简称状态机， 是表示有限个状态以及在这些状态之间的转移和动作是表示有限个状态以及在这些状态之间的转移和动作 等行为的数学模型。等行为的数学模型。 状态：存储关于过去的信息，就是说状态：存储关于过去的信息，就是说, ,它反映从系它反映从系 统开始到现在时刻的输入变化。统开始到现在时刻的输入变化。 转移转移: :指示状态变更，并且用必须满足来确使转移指示状态变更，并且用必须满足来确使转移 发生的条件来描述它。发生的条件来描述它。 动作动作: :

15、是在给定时刻要进行的活动的描述。有多种是在给定时刻要进行的活动的描述。有多种 类型的动作：类型的动作： n进入动作（进入动作（Entry actionEntry action）- -在进入状态时进行在进入状态时进行 n退出动作退出动作 - -在退出状态时进行在退出状态时进行 n输入动作输入动作 - -依赖于当前状态和输入条件进行依赖于当前状态和输入条件进行 n转移动作转移动作 - -在进行特定转移时进行在进行特定转移时进行 16 为了描述一个有限状态机的工作状况，可采用为了描述一个有限状态机的工作状况，可采用 。状态转换图是一个有向图，图中的每个节。状态转换图是一个有向图，图中的每个节 点表示

16、一种状态，一条边（或弧）表示一个转换关点表示一种状态，一条边（或弧）表示一个转换关 系。系。 初始状态通常用初始状态通常用 “没有起点的箭头没有起点的箭头” 指向它来表示指向它来表示。 终止状态是机器终止状态是机器 完成了它的程序之后完成了它的程序之后 的状态，它通常表示的状态，它通常表示 为双重圆圈。为双重圆圈。 q0 q1 q3 q2 aa b b b 状态转换图状态转换图 a 17 状态表状态表 除了状态转换图以外除了状态转换图以外, ,还可以使用多种类型的状态转还可以使用多种类型的状态转 移表。最常见的表示如下：移表。最常见的表示如下： 当前状态和条件的组合指示出下一个状态。当前状态和

17、条件的组合指示出下一个状态。 完整的动作信息可以只使用脚注来增加。完整的动作信息可以只使用脚注来增加。 状态转移表状态转移表 当前状态当前状态 条件条件 状态状态 A状态状态 B状态状态 C 条件条件 X 条件条件 Y状态 C 条件条件 Z 18 FSMFSM有两个不同的类别：接受器识别器和变换器。有两个不同的类别：接受器识别器和变换器。 接受器产生一个二元输出，说要么接受器产生一个二元输出，说要么“是是”要么要么“否否”来来 回答输入是否被机器接受。回答输入是否被机器接受。 在所有输入都被处理了的时候，在所有输入都被处理了的时候， 如果当前状态是接受状态，输入被接受；如果当前状态是接受状态，

18、输入被接受； 否则被拒绝。否则被拒绝。 作为规则，输入是符号作为规则，输入是符号 （字符）；动作不使用。（字符）；动作不使用。 接受器状态机接受器状态机 q0 q1 q3 q2 aa b b b Err 非非a或或b a 19 变换器使用动作基于给定输入和或状态生成输出。常变换器使用动作基于给定输入和或状态生成输出。常 分为两种类型：分为两种类型：Moore机和机和Mealy机。机。 Moore机机-只使用进入动作的只使用进入动作的FSM，就是说输出只依赖于，就是说输出只依赖于 状态。状态。Moore 模型的好处是行为的简单性。模型的好处是行为的简单性。 例：一个电梯门的例：一个电梯门的 Mo

19、ore FSM。 状态状态“Opening”中的进入中的进入 动作动作 (E:) 开启电机开门，开启电机开门， 在状态在状态“Closing”中的进入中的进入 动作以反方向开启电机关门。动作以反方向开启电机关门。 状态状态“Opened”和和“Closed” 不进行任何动作。不进行任何动作。 变换器状态机（变换器状态机（1） q0 opening cmd_open cmd_close closeing 开门 关门 opened closed 20 Mealy机机-只使用输入动作的只使用输入动作的FSM，就是说输出依赖于输，就是说输出依赖于输 入和状态。入和状态。 Mealy FSM 的使用经常

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

21、）自动机。在确定型自动机）自动机。在确定型自动机 中，每个状态对每个可能输入只有精确的一个中，每个状态对每个可能输入只有精确的一个 转移。在非确定型自动机中，给定状态对给定转移。在非确定型自动机中，给定状态对给定 可能输入可以没有或有多于一个转移。可能输入可以没有或有多于一个转移。 这个区分在实践而非理论中更有用，因为存在这个区分在实践而非理论中更有用，因为存在 算法把任何算法把任何 NDFA 转换成等价的转换成等价的 DFA，尽管，尽管 这种转换一般会增加自动机的复杂性。这种转换一般会增加自动机的复杂性。 22 有限状态自动机的应用有限状态自动机的应用 有限状态自动机在很多不同领域中都是重要

22、的，有限状态自动机在很多不同领域中都是重要的， 包括电子工程、包括电子工程、 语言学、计算机科学、哲学、语言学、计算机科学、哲学、 生物学、数学和逻辑学。有限状态机是在自动生物学、数学和逻辑学。有限状态机是在自动 机理论和计算理论中研究的一类自动机。在计机理论和计算理论中研究的一类自动机。在计 算机科学中，有限状态机被广泛用于算机科学中，有限状态机被广泛用于建模应用建模应用 行为、硬件电路系统设计、软件工程，编译器、行为、硬件电路系统设计、软件工程，编译器、 网络协议、和计算与语言的研究网络协议、和计算与语言的研究。 针对许多类型的编程问题，建立有限状态自动针对许多类型的编程问题，建立有限状态

23、自动 机模型，可以为分析、求解带来很大的帮助。机模型，可以为分析、求解带来很大的帮助。 23 例例1：串口通信：串口通信 两台微机通过串口通信两台微机通过串口通信, 需在两台机器间建立需在两台机器间建立 好连接后，才可以传递数据，可以使用有限状态自好连接后，才可以传递数据，可以使用有限状态自 动机，描述串口通信的状态。动机，描述串口通信的状态。 传输数据传输数据 收到收到 应答应答 断开断开 连接连接 发出连接请求发出连接请求 q0 q1 q2 q0：空闲状态：空闲状态 q1: 等待应答状态等待应答状态 q2：通信状态：通信状态 24 例例2：打电话：打电话 (状态机在通信领域的应用状态机在通

24、信领域的应用)。 在一次呼叫中，从建立连接到通话完毕，要经在一次呼叫中，从建立连接到通话完毕，要经 历摘机，拨号，应答，进行通话等过程，话机的状历摘机，拨号，应答，进行通话等过程，话机的状 态及状态迁移如下所示。态及状态迁移如下所示。 q0q0 q1q1 q2q2 q3q3 q4q4 摘机摘机 收到拨号音收到拨号音 拨号拨号 收应答信号收应答信号 挂机挂机 收齐号码收齐号码 q0:q0:空闲状态空闲状态 q1:q1:等待拨号音状态等待拨号音状态 q2:q2:可以拨号状态可以拨号状态 q3:q3:等待应答状态等待应答状态 q4:q4:通话状态通话状态 状态迁移状态迁移 状态状态 25 接受器接受

25、器有限状态机的形式化定义有限状态机的形式化定义 一个五元组一个五元组 其中：其中： ：有限的状态集合；：有限的状态集合； ：有限的输入字母表；：有限的输入字母表； ： 转换函数，是转换函数，是 到到 的映射；的映射； ： 初始状态，初始状态， ； ： 终止状态集，终止状态集， ； Q T 0 q F TQQ QF 接受器的形式化定义接受器的形式化定义 Qq 0 ),( 0 FqTQM （初始状态只有一个）（初始状态只有一个） 26 a q0 q1 q3 q2 aa b b b 状态集合状态集合 字母表字母表 初始状态初始状态 终止状态集终止状态集 , 3210 qqqqQ ,baT 3 qF

26、0 q 转换函数转换函数 10 ),(qaq 20 ),(qbq 31 ),(qaq 11 ),(qbq 22 ),(qaq 32 ),(qbq ),( 3 aq),( 3 bq 例3:用于识别输入的字符串是否是 或 者 形式的有限自动机。 aab n bba n 27 程序设计实例研究程序设计实例研究 应用有限状态机模型求解问题，关键就是抽象出状态，应用有限状态机模型求解问题，关键就是抽象出状态， 描述出状态转移图和状态转移函数描述出状态转移图和状态转移函数 应用有限状态机解题步骤应用有限状态机解题步骤 1、确定输入集、确定输入集 2、绘制状态迁移图（确定状态，在每一个状态下对输入、绘制状态

27、迁移图（确定状态，在每一个状态下对输入 进行分类，确定下一个状态）进行分类，确定下一个状态） 3、确定状态转移函数（在某状态下，接收到某一字符后，、确定状态转移函数（在某状态下，接收到某一字符后， 自动机要执行的操作，以及迁移到的下一状态）自动机要执行的操作，以及迁移到的下一状态） 28 程序设计实例研究程序设计实例研究 例例4 检验输入是否是合法的检验输入是否是合法的C语言注释语言注释/*/ 导论教材P172,图10.10,注意读程序实例 q1:等待等待*状态状态 q2：注释开始状态：注释开始状态 q3: 等待等待/以结束注以结束注 释状态释状态 q4：已接收注释结：已接收注释结 束状态束状

28、态 29 程序设计实例研究程序设计实例研究 转换函数分析转换函数分析 start状态下：状态下： n输入输入/:state=q1 n输出非输出非/:state=ERROR q1状态下：状态下： n输入输入*:state=q2 n输出非输出非*:state=ERROR q2状态下：状态下： n输入输入*:state=q3 n输入输入EOF：state=ERROR n输出其他输出其他: state=q2 30 6.2 程序设计实例研究程序设计实例研究 转换函数分析转换函数分析(续）续） q3状态下：状态下： n输入输入*:状态不变状态不变 n输入输入/:state=q4 n输入输入EOF：stat

29、e=ERROR n输出其他输出其他: state=q2 q4状态下：状态下： n输入输入EOF：state=ACCEPT n输出其他输出其他: 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、状态机模型的思路和人解决问题的思路是一致的，都、状态机模型的思路和人解决问题的思路是一致的，都 是把复杂的问题逐步分解为简单的步骤。所以状态机模是把复杂的问题逐步分解为简单的步骤。所以状态机模 型是程序员的好助手，不是你的竞争对手。型