有限自动机的应用ppt课件.ppt

有穷自动机的应用 1 自动机的介绍 1 什么是自动机 自动机是有限状态机 FSM 的数学模型 百度百科 2 自动机的介绍 2 自动机的由来 一 二十世纪六七十年代 美国语言学家N 乔姆斯基等人建立了形式文法和自动机之间的联系 证明语言的形式文法与自动机之间存在着如下的对应关系 若某一语言能用图灵机来识别 则它就能用O型文法生成 反之亦然 若某一语言能用线性有界自动机来识别 则它就能用上下文敏感文法生成 反之亦然 N 乔姆斯基 3 自动机的介绍 2 自动机的由来 二 若某一语言能用后进先出自动机来识别 则它就能用上下文自由文法生成 反之亦然 若某一语言能用有限自动机来识别 则它就能用有限状态文法生成 反之亦然 这种关于形式文法与自动机的关系 反映了语言的生成过程与识别过程的内在联系 它已成为计算机科学的基石之一 这是语言学对于现代自然科学发生影响的一个明证 4 自动机的介绍 5 有穷自动机的介绍 有穷自动机 是LEX转换的核心 其本质上是与状态转换图类似的图有穷自动机的分类 不确定的有穷自动机 NFA 确定的有穷自动机 DFA 6 相应的语言 L aa bb 有穷自动机的介绍 7 有限状态自动机在很多不同领域中都是重要的 包括电子工程 语言学 计算机科学 哲学 生物学 数学和逻辑学 有限状态机是在自动机理论和计算理论中研究的一类自动机 在计算机科学中 有限状态机被广泛用于建模应用行为 硬件电路系统设计 软件工程 编译器 网络协议 和计算与语言的研究 针对许多类型的编程问题 建立有限状态自动机模型 可以为分析 求解带来很大的帮助 骚年好好学吧 8 TMD说清楚点 到底肿么用 9 非确定有穷自动机 NFA由以下几部分组成 五要素 一个有穷状态集合S一个输入字母表 inputalphabet 转换函数 transitionfunction 对于每个状态和 U 中的符号 给出相应的后继状态集合初始状态s0有些定义中可以有多个开始状态接受状态集合FF S 10 转换表 transitiontable 表示法 用二维表表示NFA的转换函数每行对应于一个状态 每列对应于一个输入符号或者 每个条目表示对应的后继状态集合 转换表表示法 11 NFA的例子 状态集合S 0 1 2 3 开始状态0接受状态集合 3 转换函数 0 a 0 1 0 b 0 1 b 2 2 b 3 相应的图形表示 貌似很深奥 12 妹的什么是 尼玛能不能说的简单点 13 例1 打电话 状态机在通信领域的应用 在一次呼叫中 从建立连接到通话完毕 要经历摘机 拨号 应答 进行通话等过程 话机的状态及状态迁移如下所示 状态迁移 状态 14 如果你还觉得难以理解 见到美女 见美女走后 15 设备管理系统 是对设备从购入 报废整个使用过程进行全面管理的计算机信息管理系统 设备在其使用过程的现状不断发生改变 因而使设备管理具有很强的动态化特征 如果在系统分析阶段不能对设备生命周期的状态变换过程做出准确 清晰的描述 将会导致运行阶段非法操作的出现 甚至会引起管理过程的混乱 造成设备信息的破坏 因此 成功开发设备管理系统的关健在于对设备管理的全过程做出正确的分析和描述 有穷自动机在 设备管理系统 开发中的应用 还是直接跳过这一段吧 16 将设备在其整个使用周期中可能其有的各种现状作为M的状态集K K 在用 待修 待废 报废 丢失 将现有设备管理有关的业务处理作为M的输入字母表 括号中的字母为该业务处理的代号 待修处理 a 待废申请 b 报失处理 c 修复登记 d 报废