《08-第三章有限自动机与词法分析器.ppt》由会员分享，可在线阅读，更多相关《08-第三章有限自动机与词法分析器.ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 有穷自动机有穷自动机与词法分析器与词法分析器任课教师任课教师王养廷王养廷主要内容主要内容1.非确定有穷自动机非确定有穷自动机2.NFA到到DFA转换转换1 非确定有穷自动机非确定有穷自动机n非确定有穷自动机（非确定有穷自动机（NFA）定义：定义：一个状态的不同输出边标有相同的字符一个状态的不同输出边标有相同的字符允许边上标有空字符允许边上标有空字符特点特点对一个状态，接受一个字符后可以有多个对一个状态，接受一个字符后可以有多个状态状态1 非确定有穷自动机（续）非确定有穷自动机（续）n举例举例2 NFA到到DFA转换（续）转换（续）n闭包的算法闭包的算法闭包：闭包：闭包：闭包：举例
2、举例2 NFA到到DFA转换（续）转换（续）n闭包闭包假设给定一个非确定自动机假设给定一个非确定自动机NFA和和NFA的一的一个状态集合个状态集合SS，则可定义，则可定义SS的的闭包。记为闭包。记为close_(SS)2 NFA到到DFA转换（续）转换（续）n闭包的算法闭包的算法令令close_(SS)包含包含SS若若S close_(SS)且有且有SS1，则令，则令S1属属于于close_(SS)最后最后close_(SS)中没有一个状态中没有一个状态S有有边指边指向向close_(SS)之外的状态之外的状态n说明说明计算状态集合的计算状态集合的闭包闭包2 NFA到到DFA转换（续）转换（续
3、）n举例举例2 NFA到到DFA转换（续）转换（续）n举例举例close_(1)=1，2，3，4close_(2)=1，2，3，4close_(3)=1，2，3，4close_(4)=1，2，3，4close_(5)=5，6，7close_(6)=6，72 NFA到到DFA转换（续）转换（续）nNFA到到DFA转换算法转换算法算法算法P42讲解算法讲解算法P42例子例子分析算法执行过程分析算法执行过程例：例：a*b*2 NFA到到DFA转换（续）转换（续）nDFA极小化极小化状态等价状态等价状态集划分状态集划分方法方法P45例子例子分析算法执行过程分析算法执行过程总结总结n总结总结NFANFA到到DFA转换转换n重点重点NFA到到DFA转换转换n作业作业P60 3(1),(3),(5),6,7,8