3.3 3.3 有有 限限 自自 动动 机机3.3有有限限自自动动机机 3.3.1不确定的有限自动机（简称不确定的有限自动机（简称NFA）一个数学模型，它包括：一个数学模型，它包括：1、有限的状态集合、有限的状态集合S2、输入符号集合、输入符号集合 3、转换函数、转换函数move:S ( )P(S)4、状态、状态s0是唯一的开始状态是唯一的开始状态5、F S是接受状态集合是接受状态集合识别语言识别语言(a|b)*ab的的NFA12开始开始a0abb一个符号标记离开同一状态有多条边输输 入入 符符 号号ab00, 10122状状态态 NFA的转换表的转换表3.3有有限限自自动动机机 识别语言识别语言(a|b)*ab的的NFA12开始开始a0abb3.3有有限限自自动动机机 v例例 识别识别aa* *| |bb* *的的NFA12开始开始a0abb34 3.3.2确定的有限自动机（简称确定的有限自动机（简称DFA) ) 一个数学模型，包括：一个数学模型，包括：1、有限的状态集合、有限的状态集合S2、输入字母集合、输入字母集合 3、转换函数、转换函数move :S S，且可以是部分函数且可以是部分函数4、唯一的开始状态、唯一的开始状态s05、接受状态接受状态集合集合F S12开始开始a0abbab识别语言识别语言(a|b)*ab的的DFA3.3有有限限自自动动机机 一个符号标记离开同一状态只有一条边3.3有有限限自自动动机机 v例例识别识别(a | b)* a b 的DFA3.3有有限限自自动动机机 v例例识别识别(a | b)* a b 的DFADFANFA练习v叙述0(0|1)*0和(|0)1*)*描述的语言v一个语言的非形式定义是：字母表0,1上所有不含字串001的0和1的串，写出定义该语言的正则表达式练习v构造一个DFA，他接受=0,1上的0和1的个数是偶数的字符串。v构造一个DFA，他接受=0,1上能被5整除的二进制数。简单起见，00101也是可以被接受的。v构造一个DFA，他接受=0,1上所有大于5的二级制数。v有/*开始，*/结束的串构成C语言的注释，中间没有*/，画出接受注释的DFA。练习v某系统下合法的文件名为vdevice：name. extensionv其中第一部分和第三部分可以省略，画出识别这种文件名的DFA。重点v有限自动机v不确定有限自动机（NFA）v确定有限自动机（DFA）v初步掌握通过描述，绘制有限自动机的状态转换图结束语结束语谢谢大家聆听！谢谢大家聆听！12