33有限自动机 今例识别(a|b)*ab的DFA DEA b 开始 a NFA 开始
3.3 有 限 自 动 机 ❖ 例 识别 (a | b)* a b 的DFA DFA NFA
NFA到DFA——子集构造法
NFA到DFA——子集构造法
33有限自动机 333NFA到DFA的变换 子集构造法 1、DFA的一个状态是NFA的一个状态集合 2、读了输入a1a2…,an后, NFA能到达的所有状态:s1S2,…,sk则 DFA到达状态{s1,S2,…,sh} a 0} {0, 开始 b 0 b b未画完 {0,2 b
3.3.3 NFA到DFA的变换 子集构造法 1、DFA的一个状态是NFA的一个状态集合 2、读了输入a1 a2 … an后， NFA能到达的所有状态：s1 , s2 , …, sk，则 DFA到达状态{s1 , s2 , …, sk } 1 2 开始 a 0 a b {0} {0, 1} b a b a {0, 2} b 3.3 有 限 自 动 机 未画完
33有限自动机 333NFA到DFA的变换 子集构造法 运算 描述 8- closure(s 从NFA的状态s出发,只用c转换能到达的NFA状态集合 e-closure(t NFA的状态集合{ss∈ε-coe(b)&∈T move(t, a) A的状态集合{s|s=moe(t,a)&∈Ty
3.3 有 限 自 动 机 3.3.3 NFA到DFA的变换 子集构造法
子集构造法 E-closure(s)从NFA的状态S出发,只用ε转换就能到达的 状态的集合 E-closure(T从NFA的状态集合T中每个状态出发,只用E 转换就能到达的状态的集合 Move(T,a)状态集合T中每个状态通过a能到达的所有状态 集合 开始 6 b 4
子集构造法 ❖ ε-closure(s) 从NFA的状态S出发，只用ε转换就能到达的 状态的集合 ❖ ε-closure(T) 从NFA的状态集合T中每个状态出发，只用ε 转换就能到达的状态的集合 ❖ Move(T,a) 状态集合T中每个状态通过a能到达的所有状态 集合 1 9 开始 0 a b a b 6 7 8 2 3 4 5