从正则表达式到有限自动机 3.7~3.9
从正则表达式到有限自动机 3.7~3.9
有限旬动机
有限自动机
33有限自动机 331不确定的有限自动机(简称NFA) 个数学模型,它包括:一个符号标记离开同一状态有多条边 1、有限的状态集合S 2、输入符号集合∑ 3、转换函数move:S×(Σ∪{e})→P(S) 4、状态s是唯一的开始状态 5、FcS是接受状态集合a 识别语言 (ab ab 开始(0)a(1 ②2 的NFA b
3.3 有 限 自 动 机 3.3.1 不确定的有限自动机（简称NFA） 一个数学模型，它包括： 1、有限的状态集合S 2、输入符号集合 3、转换函数move : S ( {} ) → P(S) 4、状态s0是唯一的开始状态 5、F S是接受状态集合 识别语言 (a|b) *ab 的NFA 开始 1 2 a 0 a b b 一个符号标记离开同一状态有多条边
33有限自动机 NFA的转换表 输入符号 状态 {0,1} b 识别语言 (a b) ab (0 b@2 的NFA b
输 入 符 号 a b 0 {0, 1} {0} 1 {2} 2 状 态 • NFA的转换表 3.3 有 限 自 动 机 识别语言 (a|b) *ab 的NFA 开始 1 2 a 0 a b b
33有限自动机 332确定的有限自动机(简称DFA) 个数学模型,包括:一个符号标记离开同一状态只有一条边 1、有限的状态集合S 2、输入字母集合∑ 3、转换函数move:SxΣ→S,且可以是部分函数 4、唯一的开始状态S 5、接受状态集合FcSb b 识别语言 开始 b 0 (ab) ab 的DFA
3.3.2 确定的有限自动机（简称DFA) 一个数学模型，包括： 1、有限的状态集合S 2、输入字母集合 3、转换函数move : S → S，且可以是部分函数 4、唯一的开始状态 s0 5、接受状态集合F S 1 2 开始 a 0 a b b a b 识别语言 (a|b) *ab 的DFA 3.3 有 限 自 动 机 一个符号标记离开同一状态只有一条边
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