北京邮电大学形式语言自动机课件.ppt

* * * * 从图中可以看到两个最短解是：从初始状态到终止状态的最短路径。实际上，问题存在无穷多个不同的解。因此可以认为有限状态系统定义了一个无穷的语言，这个语言是由那些能使状态从初始状态经过任意可能的路径到达终止状态的字符串组成。 在上面的例子中，至少有两点不应作为有限状态系统的一般形式。首先，例中仅有一个终止状态，而一般可以不止一个；其次，例中每个状态的转移，在同一输入符号作用下，都存在反向的，这在一般情况下是不需要的。此外，注意“终止状态”这一术语并不意味着一旦抵达这个状态演算就必须停止。如上例中的终止状态 Φ一MWGC，在g的作用下可以继续转移到状态MG—WC。 * * * * * * College of Computer Science Technology, BUPT * * College of Computer Science Technology, BUPT 第三章 有限自动机与右线性文法 本章主要内容 确定有限自动机 非确定有限自动机 确定与非确定有限自动机的等价性 右线性文法和有限自动机的等价性， 右线性文法的性质(泵浦定理) 使用归纳法进行证明的方法。 * * College of Computer Science Technology, BUPT 第一节 有限自动机 一、有限状态系统的概念 状态:状态是可以将事物区分开的一种标识。 具有离散状态的系统:如数字电路(0,1), 十字路口的红绿灯。离散状态系统的状态数是有限的. 具有连续状态的系统:比如水库的水位,室内温度等可以连续变化,即有无穷个状态. 有限状态系统必然是离散状态系统（而且状态数有限）,因为只有有限个状态. * * College of Computer Science Technology, BUPT 实例 一个人带着一头狼，一头羊，以及一棵青菜，处于河的左岸。有一条小船,每次只能携带人和其余的三者之一。人和他的伴随品都希望渡到河的右岸，而每摆渡一次，人仅能带其中之一。然而如果人留下狼和羊不论在左岸还是在右岸，狼肯定会吃掉羊。类似地，如果单独留下羊和菜，羊也肯定会吃掉菜。如何才能既渡过河而羊和菜又不被吃掉呢? * * College of Computer Science Technology, BUPT MG－WC （处于左岸的子集－处于右岸的子集） 将过河问题模型化： 人(M) 狼(W) 羊(G) 菜(C) * * College of Computer Science Technology, BUPT 二、有限自动机的概念 有限自动机的概念 具有离散 输入 输出系统的一种数学模型 (可以没有输出，比较特殊的也可以没有输入). 有限的状态 状态+输入?状态转移 每次转换的后继状态都唯一 ? DFA 每次转换的后继状态不唯一 ? NFA * * College of Computer Science Technology, BUPT FA的模型 FA可以理解成一个控制器,它读一条输入带上的字符。 101101 有限 控制器 (1) 控制器包括有限状态; (2) 从左到右依次读取字符; (3) 状态+激励 ? 状态迁移 (根据当前所处状态和输入字符进行状态转移) * * College of Computer Science Technology, BUPT 有限状态集 有限输入符号集 转移函数 一个开始状态 一个终态集合 有限自动机的五要素 q0 q1 q2 q3 * * College of Computer Science Technology, BUPT 三、DFA的形式定义 定义: DFA是一个五元组 M=(Q,T,δ,q0,F) Q: 有限的状态集合 T: 有限的输入字母表 δ: 转换函数(状态转移集合): Q×T ? Q q0: 初始状态， q0 ? Q F: 终止状态集, F ? Q * * College of Computer Science Technology, BUPT 转 移 图 表 示 的 DFA Q = {q0 , q1 , q2 , q3 } T = {0, 1 } ? (q0 ,0) = q2 , ? (q0 ,1) = q1 ? (q1 ,0) = q3 , ? (q1 ,1) = q0 ? (q2 ,0) = q0 , ? (q2 ,1) = q3 ? (q3 ,0) = q1 , ? (q3 ,1) = q2 q0 F = {q0 , q3 } q0 q1 q2 q3 * * College of Computer Science Techno