形式语言与自动机week4-ch3.7-3.9a精要.ppt

fall 2001 *College of Computer Science Technology, BUPT 正则表达式与有限自动机的关系 右线性语言与有限自动机的关系 右线性语言的性质(part1) 第四讲 3.7 正则表达式与有限自动机的关系 结论: 有限自动机、右（左）线性文法、正则表达式都定义了同一种语言-- 正则语言 . 证明策略 ? - NFA NFA DFA RE RE( Regular Expression) --- 正则表达式 从 DFA 构造等价的正则表达式 （状态消去法） 思路: (1) 扩展自动机的概念，允许正则表达式作为转移弧的标记. 这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变. (2) 在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补. 以下分别介绍中间状态的消去与正则表达式构造过程. 从 DFA 构造等价的正则表达式 （中间状态的消去） x y r1r2 x z r1 y r2 代之以： x y r1+r2 x y r2 r1 代之以： x y r1* x z ? y ? r1 代之以： 从 DFA 构造等价的正则表达式 （中间状态的消去） ? ? ? ? ? ? q1 qk p1 pm P1 Pm Qk Q1 R11 R1m Rkm Rk1 ? ? ? R11+ Q1S* P1 R1m+ Q1S* Pm Rkm+ QkS* Pm Rk1 + QkS* P1 q1 p1 qk pm 消去 s 从 DFA 构造等价的正则表达式 （状态消去法） 步骤: (1) 对每一终态q，依次消去除 q 和初态 q0 之外的其它状态; (2) 若q? q0，最终可得到一般形式如下左图两状态自动机， 该自动机对应的正则表达式可表示为 ( R+SU*T )*SU*. (3) 若q= q0，最终可得到如下右图的自动机，它对应的正则 表达式可以表示为 R*. (4) 最终的正则表达式为每一终态对应的 正则表达式之和（并）. 状态消去法举例 对于终态C 对于终态D 等价的正则表达式 (0+1)*1(0+1)+(0+1)*1(0+1)(0+1) 状态消去法举例 0 1 3 4 2 5 6 7 a b a a b b a b ? ? ? ? 0 1 2 5 6 7 a+b a+b ? ? ? ? aa bb 0 2 5 7 (a+b)* (a+b)* aa+bb 0 7 (a+b)* (aa+bb) (a+b)* 定理: L 是正则表达式 R 表示的语言, 则存在一个? - NFA E ,满足 L(E) = L(R) = L. 证明: 构造性证明. 可以通过结构归纳法证明从 R 可以构造出与其等价的，满足如下条件的? - NFA ： (1) 恰好一个终态; (2) 没有弧进入初态； (3) 没有弧离开终态；  从正则表达式构造等价的? - NFA 基础: 从正则表达式构造等价的? - NFA （归纳构造过程） 1 对于 ? ，构造为 ? 3 对于 a ，构造为 a 2 对于 ? ，构造为 归纳: 从正则表达式构造等价的? - NFA （归纳构造过程） 1 对于 R+S ，构造为 ? ? ? ? 归纳: 从正则表达式构造等价的? - NFA （归纳构造过程） 2 对于 RS ，构造为 ? 3 对于 R* ，构造为 ? ? ? ? 举例: 设正则表达式 1*0(0+1)*, 构造等价的? - NFA. 从正则表达式构造等价的? - NFA 0+1 ? ? ? ? 1* ? ? ? ? 从正则表达式构造等价的? - NFA (0+1)* ? ? ? ? ? ? ? ? 1*0(0+1)* ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3.8 右线性语言与有限自动机 至此，我们已学到正则集有三种定义方式，且这三种方式等价： 正则集是含有{ε}，φ，{a} 以及在并、连接和 * 运算下封闭的语言 由正规表达式定义的集合是正则集。 由右线性文法生成的语言是正则集。 此外，还有第四种方式： 将正则集作为由有限自动机定义的集合。 即 正则集(右线性语言) ＝ 有限自动机 右线性文法＝ 有限自动机 定理3.8.1：由任意右线性文法G定义的语言必然能被一个NFA M所接受。即L（G）＝L（M） 证明思路（构造证明）： 设右线性文法G＝（N，T，P，S），构造一个与