另一种方法-状态机PPT演示课件

另一种方法,状态机介绍,1,最简单的例子,字符串识别匹配串A+B*C+状态：5个事件：7个A/B/C/A/BC/EOS/EOS处理：2个,2,另一个简单例子(1),门禁控制程序刷卡、开门、关门按钮、开门、关门超时报警身份不对提示手动开门、自动关门,3,另一个简单例子(2),7个状态11次状态迁移10种事件响应5个处理方法,4,另一个简单例子(3),程序设计状态起始、结束、关闭、确认中、开门中、关门中、报警事件启动、停止、关门完毕、开门完毕、按钮按下、刷卡、确认成功、确认失败、开门超时、关门超时处理开门允许、开门禁止、成功提示、失败提示、超时报警,5,另一个简单例子(4),程序设计状态一个状态一个函数StateClosed/StateOpening/StateAlerting函数中响应该函数所需要处理的事件(以关闭状态为例)OnEventPushbuttonOnEventRFCardInput函数或状态转换过程进行处理(以开门中状态为例)设置允许开门AllowOpen,6,另一个简单例子(5)问题,大材小用？如果能自动化地进行状态机的设计，结果会是如何？实际上包括正则表达式等文字匹配的工作都是使用状态机进行处理的，状态机可以依据匹配串进行自动化构建，它可以处理人力所无法承受的设计工作。尝试一下这个：(u4E00-u9FA5&与及+?国省市区县)+公安部厅局(u4E00-u9FA5&与及+?(?:分局|派出所|大中总支队)*),7,小结(1),用状态机方法进行设计的特点1.全面设计，极大地减少遗漏2.直观设计，比文字或代码的表现力强一数量级3.设计转换为程序的过程非常简单4.调试方便，能够快速定位5.没有看到设计的人看不懂程序可能性很大，尤其是大型状态机设计程序的正确性完全依赖于设计的正确性,8,状态机设计的应用范围,状态机应用环境适合于多阶段的应用1.网络协议2.事件驱动3.网络应用语言处理自然语言/程序语言实际上是全范围实用计算机（包括程序）都是状态机,9,状态机设计的要素,状态机要素状态定义（S）States事件定义（E）Event状态迁移（T）Transfer初始状态（S0）结束状态（F）Finalized事务处理（A）Action,10,真实例子网络文件传输,保证送达分包发送容错,主循环状态,11,真实例子网络文件传输,子状态-单文件发送,12,小结(2),状态机设计与流程图设计的比较更加抽象基本图元素只有三个：状态、迁移、条件（行为）适合事务具有多个中间环节自包含分支条件无需表达分支与条件状态机：设计；流程图：实现,13,几个例子(1)问题记录,问题状态实际上，我们不自觉地使用状态机进行处理,14,几个例子(2)进程状态,操作系统中进程的状态控制,15,实际例子输入法主状态机,16,手机输入法的主要状态机,DEL/SEL/R/L+-+con/wov(P2)|+-+-+|Del(C2)(P5)|Del(C2)(P5)+-+|+-+|+-+|-+SEP(P10)|S|-|-|1|-|4|-+|(P0)|-+-|-+|3|-+|+-+|+-+|Up/Down(P32)|v|Up/Down(P9)|+-+-+|+-+,17,自动机介绍(1),自动机由图灵发明初衷是为了解决可计算性问题其中比较有名的一个问题为：如何判定一个程序是否停止。图灵证明了这个判定程序是不存在的。推论：完全的自动测试程序同样是不存在的。,18,自动机介绍(2),图灵自动机的基本构件输入：无限长的纸带，纸带上的符号：0、1行动：打印头打印0、1，并向左或右移动状态：起始、结束以及有限个中间状态迁移：每一个状态中，面对纸带上的符号，采取响应的动作，移动以及打印。该自动机可以完成所有当前计算机能够做的事情，是计算机的一个理想抽象。,19,自动机介绍(3),图灵自动机例子该图灵机完成验证100110的符号串,20,自动机介绍(4),竞赛：80年代初期，有好事者举办了一个竞赛，谁能够使用4个状态（不含停止状态）的图灵机打印出最多的1，为获胜者一年的时间，最后的获胜者打印出来514个1.作者认为不可能有超过这个结果的图灵机。是否可信？,21,自动机介绍(5),练习题目：无限长的纸带上除了一个1以外其他都是0。编写一个图灵自动机，在有限的步骤内擦除这个1，使得全部纸带上的符号都是0。,22,实际练习电梯控制,