编译原理 第3章 词法分析与有穷自动机(第5-8讲).ppt

* ■由正规表达式R构造NFA (a)对于正规式φ,所构造NFA: x y (b)对于正规式ε,所构造NFA: x y ε (c)对于正规式a,a∈Σ,则 NFA: x y a 1.基本正规表达式 * ■由正规表达式R构造NFA 2、若r,s为正规式： 1 2 3 r s s r 1 3 rs r|s r* 例：构造与正规表达式R=ab*a(a|b)*等价的NFA。 1 r 3 2 ε ε * 为R=(a|b)* (aa|bb) (a|b)* 构造NFA,使得L(N)=L(R) ■课堂练习 ■课后作业 P55 3.1(1)(2) * ■ NFA确定化为DFA的方法 非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的。 NFA M’ DFA M 构造成一个 使得 L(M)=L(M’) * 定义1：状态集合I的ε-闭包： 令I是一个状态集的子集，定义ε-closure（I）为： 1）若s∈I，则s∈ε-closure（I）； 2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。 状态集ε-closure（I）称为I的ε-闭包 为了使得NFA确定化，给出两个定义： 5 6 4 3 2 a ε a a ε 1 例：如图所示的状态图： 令I={1}，求ε-closure（I）=？ 解：根据定义： ε-closure（I）={1，3} 例：若I1={1,2}，则 ε-closure（I1）={1,2,3,6} * —— J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合。 —— Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过ε弧到达的状态。 定义2: 状态子集的构造： s∈I 例：令I={1}，求Ia=? Ia=ε-closure(J) =ε-closure(T(1，a)） =ε-closure({2，4}） ={2，4，6} 5 6 4 3 2 a ε a a ε 1 令I是NFA M’的状态集的一个子集, a∈Σ 定义: Ia=ε-closure(J) 其中J = ∪T(s,a) * 例：有NFA M，求DFA M’。 a 1 2 3 4 start a b a c c ε I Ia Ib Ic {1,4} {2,3} φ φ {2,3} {2} {4} {3,4} {2} {2} {4} φ {4} φ φ φ {3,4} φ φ {3,4} 初态 I=ε-closure({1})={1,4} Ia=ε-closure(T(1,a)∪T(4,a)) = ε-closure({2,3}∪φ） = ε-closure ({2,3}) ={2,3} Ib= ε-closure(T(1,b)∪T(4,b)) = ε-closure(φ） =φ Ic= ε-closure(T(1,c)∪T(4,c)) = φ I={2,3}, Ia={2},Ib={4},Ic={3,4}… … DFA的状态 P42 * 符号 状态 a b c 0 2 3 4 1 2 2 1 _ _ _ _ _ _ _ _ 3 3 4 4 ● DFA M’状态表 将求得的状态转换矩阵重新编号 start 0 1 4 2 3 {1,4} {2,3} {4} {2} a c a b b c {3,4} I Ia Ib Ic {1,4} {2,3} φ φ {2,3} {2} {4} {3,4} {2} {2} {4} φ {4} φ φ φ {3,4} φ φ {3,4} 包含NFA终态的状态子集全都是DFA的终态。 * ■ DFA的化简 自动机理论中的结论： 对于任一个DFA M，存在一个唯一的状态最少的等价的DFA M’ 即：一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个