week2第三章有限自动机(阅读).ppt

fall 2001 第三章 有限自动机与右线性文法 本章主要内容 确定有限自动机 非确定有限自动机 确定与非确定有限自动机的等价性 右线性文法和有限自动机的等价性， 右线性文法的性质(泵浦定理) 使用归纳法进行证明的方法。 第一节 有限自动机 一、有限状态系统的概念 状态:状态是可以将事物区分开的一种标识。 具有离散状态的系统:如数字电路(0,1), 十字路口的红绿灯。离散状态系统的状态数是有限的. 具有连续状态的系统:比如水库的水位,室内温度等可以连续变化,即有无穷个状态. 有限状态系统必然是离散状态系统（而且状态数有限）,因为只有有限个状态. 第一节 有限自动机 实例 一个人带着一头狼，一头羊，以及一棵青菜，处于河的左岸。有一条小船,每次只能携带人和其余的三者之一。人和他的伴随品都希望渡到河的右岸，而每摆渡一次，人仅能带其中之一。然而如果人留下狼和羊不论在左岸还是在右岸，狼肯定会吃掉羊。类似地，如果单独留下羊和菜，羊也肯定会吃掉菜。如何才能既渡过河而羊和菜又不被吃掉呢? 二、有限自动机的概念 有限自动机的概念 具有离散 输入 输出系统的一种数学模型 (可以没有输出，比较特殊的也可以没有输入). 有限的状态 状态+输入?状态转移 每次转换的后继状态都唯一 ? DFA 每次转换的后继状态不唯一 ? NFA FA 的模型 FA可以理解成一个控制器,它读一条输入带上的字符。 三、DFA的形式定义 定义: DFA是一个五元组 M=(Q,T,δ,q0,F) Q: 有限的状态集合 T: 有限的输入字母表 δ: 转换函数(状态转移集合): Q×T ? Q q0: 初始状态， q0 ? Q F: 终止状态集, F ? Q 表示方法： 转 移 图 表 示 的 DFA 四、扩展转移函数适合于输入字符串 δ’函数：接收一个字符串的状态转移函数。 ??: Q ? T* ? Q 对任何q ? Q，定义： 1. ?? (q , ? ) = q 2. 若ω是一个字符串, a是一个字符 定义: δ’(q,ωa)=δ(δ’(q,ω),a) 对于DFA:δ’(q,a)=δ(δ‘(q, ? ),a)=δ(q,a)，即对于单个字符时δ和δ是相等的。为了方便，以后在不引起混淆时用δ代替δ 扩展转移函数适合于输入字符串 DFA接受的语言 被DFA接收的字符串: 输入结束后使DFA的状态到达终止状态。否则该字符串不能被D FA接收. DFA接收的语言: 被DFA接收的字符串的集合. L(M) = ? ω ? ?? ( q0 , ω) ? F ? 例：T = {0，1} 五、格局 为描述有限自动机的工作过程，对于它在某一时刻的工作状态，可用两个信息表明：当前状态q，待输入字符串ω。两者构成一个瞬时描述，用（q, ω）表示，称为格局。 初始格局：（q0, ω) 终止格局： (q,ε), q?F 如图，接受001010的格局 （q0,001010）┝ (q2,01010) ┝ (q0,1010) ┝ (q1,010) ┝ (q3,10) ┝ (q2,0) ┝ (q0,ε) 格局数量是无限的。 有限状态自动机是无记忆的。例如接受0010101111和接，都可以进入格局(q0,1111)。 设计有限自动机 自动机的设计是一个创造过程，没有简单的算法或过程。 技巧：假设自己是机器，思考如何去实现机器的任务。 为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。 例：构造自动机，识别所有由奇数个a和奇数个b组成的字符串。 关键：不需要记住所看到的整个字符串，只需记住至此所看到的a、b个数是偶数还是奇数。 设计有限自动机 例2：构造有限自动机M，识别{0,1}上的语言 L={x000y | x,y∈{0,1}*} 分析：该语言特点是每个串都包含连续3个0的子串，自动机的任务是识别/检查是否存在子串000。 由于字符是逐一读入，当读入一个0时，就需记住（状态q1), 若接着读入的还是0，则需记住已读入连续的2个0了（状态q2),若接着读入的还是0，则需记住已读入连续的3个0了（状态q3), 设计有限自动机 例3：构造有限自动机M，识别{0,1,2}上的语言,每个字符串代表的数字能整除3。 分析：如果一个十进制数的所有位的数字之和能整除3，则该十进制数就能整除3。 一个十进制数除以3，余数只能为0、1、2。---设计为状态。 状态q0表示已读入的数字和除3余0, 状态q1表示已读入的数字和除3余1, 状态q2表示已读入的数字和除3余2, 第二节 不确定的有限自动机(NFA) 修改DFA的模型,使之在某个状态, 对应一个输入,