有限状态机应用.ppt

1 大作业 文件IO版本设计思路 3 7 2020 2 大作业文件IO版本模块结构图 3 7 2020 3 大作业文件IO版本程序框架 大作业文件IO版本的程序主体结构 structSTATE 电梯或银行的运行状态structLIST 请求队列链表节点structREQ 暂存每次获得的请求事件intmain inttimeCount 0 计时器 每循环一次模拟2msstructREQtheReq 暂存每次获得的请求事件structSTATEpreST theST 保存电梯或银行的运行状态structLIST headp NULL 存请求队列链表头指针File fpin fpout 3 7 2020 4 大作业文件IO版本程序框架 openFile fpin fpout 打开输入输出文件theReq get fileInput fpin 读取第一个请求while endInput fpin 读取文件中的下一个请求事件 endif 3 7 2020 5 大作业文件IO版本程序框架 preST theST theST runService preST endmain 3 7 2020 6 大作业文件IO版本函数接口 intendInput File fp 判断文件输入是否结束intisIdle structSTATEstate 判断电梯或营业厅当前状态是否空闲structREQget fileInput File fp 顺序读取文件中的一个请求事件structLIST addServList structLIST hp structREQreq structSTATEstate intmode 按照策略 将新请求插入请求队列中structSTATErunService structSTATEstate structLIST hp inttime 根据状态 请求和时间条件 运行电梯或营业厅服务 运行服务后将改变的状态返回 注意当服务完一个请求后 删除该节点并修改头指针 3 7 2020 7 大作业文件IO版本函数接口 structSTATErunService structSTATEstate structLIST hp inttime 根据状态 请求和时间条件 运行电梯或营业厅服务 运行服务后将改变的状态返回 注意当服务完一个请求后 删除该节点并修改头指针 voidset fileOutput File fp inttime structSTATEstate structLIST hp 将当前时间 状态和等待队列的情况顺序写入文件 3 7 2020 8 输入文件格式定义 电梯 输入用电梯请求文件格式 文本文件 每一行表示一个时刻发生的电梯请求 格式定义如下 T CallF 例 T 1 CallF 4UT 2 CallF 4U5T请求发生时间 按程序运行的系统时钟时间 单位秒 楼层请求 由呼叫方向 U D T 和数字 1 9 组成 同时有多个请求时用空格分割 如2U5D6T 表示2层上行呼叫 5层下行呼叫 6层目标停靠 3 7 2020 9 输出文件格式定义 电梯 电梯运行结果记录文件格式 文本文件 每一行表示一个电梯停靠或启动 转向动作 当前楼层和目标楼层 以及排队的楼层请求 格式定义如下 T State NowF GoalF StopT WaitF 例 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 4U5T6U9D8D 3 7 2020 10 输出文件格式定义 电梯 当前时间 程序开始运行的系统时钟时间 单位秒 电梯状态 UP RUN表示向上运行 DOWN RUN表示向下运行 UP STOP表示上行停靠 DOWN STOP表示下行停靠 IDLE表示空闲 电梯当前楼层 1 0 9 0 停靠时间 记录电梯已经停靠的时间 单位秒 只有在停靠状态下 该信息才大于0 未响应的楼层请求 按照电梯控制策略 按响应顺序将尚未响应的呼叫请求和目标楼层列出来 是由呼叫方向 U D T 和数字 1 9 组成的序列 中间用一个空格分割 如2U5D6T 表示2层上行呼叫 5层下行呼叫 6层目标停靠 3 7 2020 11 输入文件格式定义 银行 输入用银行请求文件格式 文本文件 每一行表示一个时刻发生的客户到达事件 窗口休息请求或下班指令 格式定义如下 T Req C W Q例 T 1 Req C5T 6 Req W3T 200 Req Q250时间 按程序运行的系统时钟时间 单位秒 3 7 2020 12 输出文件格式定义 银行 银行运行结果记录文件格式 文本文件 每一行表示一个营业厅窗口的叫号 暂停休息 准备下班 进入空闲 下班等动作 各窗口状态和正在服务的客户号码 以及等待服务的客户情况 格式定义如下 T Event Now Wait JHZT KX ZB XB 3 7 2020 13 输出文件格式定义 银行 0001 9999 S0表示空闲S1表示服务S2表示暂停 策略1 策略2 例 T 3 Event JHW2C0009 Now W1S1C0004W2S2C0000W3S0C0000 Wait Q19F0010L0028 14 15 什么是有限状态自动机 FiniteStateMachine 又称有限状态机或简称状态机 是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型 状态 存储关于过去的信息 就是说 它反映从系统开始到现在时刻的输入变化 转移 指示状态变更 并且用必须满足来确使转移发生的条件来描述它 动作 是在给定时刻要进行的活动的描述 有多种类型的动作 进入动作 Entryaction 在进入状态时进行退出动作 在退出状态时进行输入动作 依赖于当前状态和输入条件进行转移动作 在进行特定转移时进行 16 为了描述一个有限状态机的工作状况 可采用状态转换图 状态转换图是一个有向图 图中的每个节点表示一种状态 一条边 或弧 表示一个转换关系 初始状态通常用 没有起点的箭头 指向它来表示 终止状态是机器完成了它的程序之后的状态 它通常表示为双重圆圈 状态转换图 a 17 状态表 除了状态转换图以外 还可以使用多种类型的状态转移表 最常见的表示如下 当前状态和条件的组合指示出下一个状态 完整的动作信息可以只使用脚注来增加 18 FSM有两个不同的类别 接受器 识别器和变换器 接受器产生一个二元输出 说要么 是 要么 否 来回答输入是否被机器接受 在所有输入都被处理了的时候 如果当前状态是接受状态 输入被接受 否则被拒绝 作为规则 输入是符号 字符 动作不使用 接受器状态机 Err 非a或b a 19 变换器使用动作基于给定输入和 或状态生成输出 常分为两种类型 Moore机和Mealy机 Moore机 只使用进入动作的FSM 就是说输出只依赖于状态 Moore模型的好处是行为的简单性 例 一个电梯门的MooreFSM 状态 Opening 中的进入动作 E 开启电机开门 在状态 Closing 中的进入动作以反方向开启电机关门 状态 Opened 和 Closed 不进行任何动作 变换器状态机 1 q0 opening cmd open cmd close closeing 开门 关门 opened closed 20 Mealy机 只使用输入动作的FSM 就是说输出依赖于输入和状态 MealyFSM的使用经常导致状态数目的简约 例 电梯门的MealyFSM有两个输入动作 开启电机关门如果command close下达 和 反向开启电机开门如果command open下达 变换器状态机 2 q0 opened cmd open 开门 cmd close 关门 closed 21 FSM的类型 在实践中经常使用混合模型 进一步可区分为确定型 DFA 和非确定型 NDFA GNFA 自动机 在确定型自动机中 每个状态对每个可能输入只有精确的一个转移 在非确定型自动机中 给定状态对给定可能输入可以没有或有多于一个转移 这个区分在实践而非理论中更有用 因为存在算法把任何NDFA转换成等价的DFA 尽管这种转换一般会增加自动机的复杂性 22 有限状态自动机的应用 有限状态自动机在很多不同领域中都是重要的 包括电子工程 语言学 计算机科学 哲学 生物学 数学和逻辑学 有限状态机是在自动机理论和计算理论中研究的一类自动机 在计算机科学中 有限状态机被广泛用于建模应用行为 硬件电路系统设计 软件工程 编译器 网络协议 和计算与语言的研究 针对许多类型的编程问题 建立有限状态自动机模型 可以为分析 求解带来很大的帮助 23 例1 串口通信两台微机通过串口通信 需在两台机器间建立好连接后 才可以传递数据 可以使用有限状态自动机 描述串口通信的状态 q0 空闲状态q1 等待应答状态q2 通信状态 24 例2 打电话 状态机在通信领域的应用 在一次呼叫中 从建立连接到通话完毕 要经历摘机 拨号 应答 进行通话等过程 话机的状态及状态迁移如下所示 状态迁移 状态 25 接受器有限状态机的形式化定义一个五元组其中 有限的状态集合 有限的输入字母表 转换函数 是到的映射 初始状态 终止状态集 接受器的形式化定义 初始状态只有一个 26 a 转换函数 例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 q2 30 6 2程序设计实例研究 转换函数分析 续 q3状态下 输入 状态不变输入 state q4输入EOF state ERROR输出其他 state q2q4状态下 输入EOF state ACCEPT输出其他 state ERROR 31 6 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形式 程序运行效果如下 例1 Pleaseinputstringconsistofa b c toend aabbcc thestringisacceptable例2 Pleaseinputstringconsistofa b c toe