从正则表达式到有限自动机 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 有 限 自 动 机 一个符号标记离开同一状态只有一条边