形式语言与自动机——有限自动机与右线性文法一.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) = ? w ? ?? ( q0 , w) ? F ? 例：T = {0，1} 五、格局 为描述有限自动机的工作过程，对于它在某一时刻的工作状态，可用两个信息表明：当前状态q，待输入字符串w。两者构成一个瞬时描述，用（q,w）表示，称为格局。 初始格局：（q0,w) 终止格局： (q,ε), q?F 如图，接受001010的格局 （q0,001010）┝ (q2,01010) ┝ (q0,1010) ┝ (q1,010) ┝ (q3,10) ┝ (q2,0) ┝ (q0,ε) 格局数量是无限的。 有限状态自动机是无记忆的。例如接受0010101111和接，都可以进入格局(q0,1111)。 设计有限自动机 自动机的设计是一个创造过程，没有简单的算法或过程。 技巧：假设自己是机器，思考如何去实现机器的任务。 为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。 例：构造自动机，识别所有由奇数个a和奇数个b组成的字符串。 关键：不需要记住所看到的整个字符串，只需记住至此所看到的a、b个数是偶数还是奇数。 第二节 不确定的有限自动机(NFA) 修改DFA的模型,使之在某个状态, 对应一个输入,可以有多个转移, 到达不 同的状态, 则称为不确定的有限自动机。 例： 一、不确定有限自动机的形式定义 NFA是一个五元组,M=(Q,T,δ,q0,F). 其中δ是Q×T-2Q的函数,其余与DFA相同. 如果接收一个字符串后NFA进入一个状态集,而此集合中包含一个以上F中的状态, 则称NFA接收该字符串. 二、NFA的状态转移函数 与 DFA 唯一不同之处 ? : Q ? T ? 2Q 同样, δ可扩展为δ’ ( ??: Q ? T* ? 2Q) 1.δ(q, ε) = {q} 含义: 不允许无输入的状态变化. 2.δ(q,ωa)={p|存在r∈δ(q,ω)∧p∈δ(r,a)} 含义:δ‘(q,ωa)对应的状态集合是δ’(q,ω)对应的每个状态下再接收字符a以后可能到达的状态集合的并集. 即 若 ?? ( q , ω) = {r 1 ,