子集构造法 找出U= E-closure(T 今对于U,以及任意符号a,找出U通过a能到达的集合 ∨=Move(Ua),并计算V=e- closure() 令U通过a到达的状态即为V,U-a->V 开始 6 b 4
子集构造法 找出U=ε-closure(T) ❖ 对于U，以及任意符号a，找出U通过a能到达的集合 V=Move(U,a) ，并计算V'=ε-closure(V) ❖ U通过a到达的状态即为V'，U- a -> V' 1 9 开始 0 a b a b 6 7 8 2 3 4 5
33有限自动机 333NFA到DFA的变换 子集构造法:状态转换表的构造 初始,ε- closure(s)是 Dstates仅有的状态,并且尚未标记; while Dstates有尚未标记的状态 t do begin 标记T for每个输入符号 a do be gin U: eclosure(move(T, a) fU不在 Dstates中then 把U作为尚未标记的状态加入 Dstates; Duran/T end
3.3 有 限 自 动 机 3.3.3 NFA到DFA的变换 子集构造法：状态转换表的构造
33有限自动机 冷例(alb)ab,NFA如下,把它变换为DFA 开始 6 b 4
❖ 例 (a|b)*ab，NFA如下，把它变换为DFA 3.3 有 限 自 动 机 1 9 开始 0 a b a b 6 7 8 2 3 4 5
33有限自动机 状态输入符号 b 开始 6 b 4
输入符号 a b 状态 3.3 有 限 自 动 机 1 9 开始 0 a b a b 6 7 8 2 3 4 5
33有限自动机 A={0,1,2,4,7 状态输入符号 b 开始 6 b 4
输入符号 a b A A = {0, 1, 2, 4, 7} 状态 3.3 有 限 自 动 机 1 9 开始 0 a b a b 6 7 8 2 3 4 5