有限自动机的应用.ppt

有穷自动机的应用 有穷自动机的介绍 有穷自动机：是LEX转换的核心，其本质上是与状态转换图类似的图 有穷自动机的分类：不确定的有穷自动机（NFA），确定的有穷自动机（DFA） 例1：打电话 (状态机在通信领域的应用)。 在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。 * * * LOGO LOGO 自动机的介绍 　　1）什么是自动机？ 　　 自动机是有限状态机(FSM)的数学模型。 —百度百科 自动机的介绍 　2）自动机的由来（一） 　　二十世纪六七十年代，美国语言学家N.乔姆斯基等人建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能用 O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然； N.乔姆斯基 自动机的介绍 　2）自动机的由来（二） 　　　③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。 　　这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。这是语言学对于现代自然科学发生影响的一个明证。 自动机的介绍 常见自动机 有限自动机 无限自动机 线性有界自动机 相应的语言：L(aa*|bb*) 有穷自动机的介绍 有限状态自动机在很多不同领域中都是重要的，包括电子工程、 语言学、计算机科学、哲学、生物学、数学和逻辑学。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。 针对许多类型的编程问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。 TMD 说清楚点！！！到底肿么用 非确定有穷自动机 NFA由以下几部分组成（五要素） 一个有穷状态集合S 一个输入字母表Σ（input alphabet） 转换函数（transition function） 对于每个状态和Σ U{ε}中的符号，给出相应的后继状态集合 初始状态s0 有些定义中可以有多个开始状态 接受状态集合F F?S 转换表（transition table）表示法 用二维表表示NFA的转换函数 每行对应于一个状态， 每列对应于一个输入符号或者ε。 每个条目表示对应的后继状态集合 转换表表示法 NFA的例子 状态集合S={0,1,2,3} 开始状态0 接受状态集合{3} 转换函数： (0,a)?{0,1} (0,b)?{0} (1,b)?2 (2,b)?3 相应的图形表示 貌似很深奥···· 妹的什么是Σ！！ 尼玛能不能说的简单点！！ q0 q1 q2 q3 q4 摘机 收到拨号音 拨号 收应答信号 挂机 收齐号码 q0:空闲状态 q1:等待拨号音状态 q2:可以拨号状态 q3:等待应答状态 q4:通话状态 状态迁移 状态 如果你还觉得难以理解··········· 见到美女 见美女走后 * * * LOGO