编译原理之有限自动机.ppt

* * * * * * * * * * * * * 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的? 转换的语法制导的算法，在将来的解题中使用这个算法。 * 《编译原理习题精选》1.5题。 * * * 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 0 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 0 1 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 0 1 0 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 0 1 0 1 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 0 1 0 1 0 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 0 1 0 1 0 1 号外：从语言到确定的有 限 自 动 机 例：识别? ={0,1}上能被能5整除的二进制数 0 1 2 3 开始 4 1 0 0 1 0 1 0 1 0 1 号外：从语言到确定的有 限 自 动 机 小结 正规式 计算机实现 状态转换图 不确定有限自动机 确定有限自动机 等价 用正规式语法结构来指导构造过程 子集构造法 合并不可区别状态 最简确定有限自动机 等价 语言 确定有限自动机 状态列举法 习 题 2.7 (c) (d), 2.8 ( 仅为2.7(c) )， 2.12（a） 练习：构造 DFA，接受 0和1的个数都是偶数的二进制串。 eg: 0011, 00, 1100, 1010, 111100 例：DFA,接受 0和1的个数都是偶数的字符串 3 1 2 0 1 1 1 1 0 0 0 0 开始 偶0偶1 奇0奇1 奇0偶1 偶0奇1 2.3 有 限 自 动 机 * * * * * * * * * * * 从转换表构造转换图。 * 从转换表构造转换图。 * 将前面的DFA和现在的DFA进行比较，引出DFA化简问题。 * 将手工构造的NFA和由算法构造的NFA进行比较，鼓励在掌握算法的同时，学会手工构造简单的DFA。 * * * * * * ____不是NFA的成分.(北航2000硕士研究生入学考题) A.有穷字母表 B.初始状态集合 C.终止状态集合 D.有限状态集合 词法分析器的输入是_____. A.单词符号 B.源程序 C.语法单位 D.目标程序 正规式M1和M2 等价是指____ A．M1和M2 的状态数相等. B．M1和M2的有向弧条数相等. C．M1和M2所表示的语言集相等. D．M1和M2的有向弧条数与状态数相等. 设∑={0,1},则∑上所有以1开头,后跟至少1个010的字符的集合对应的正规式为____. A.1(010)* B. 1(010)+ C. (010)*1 D. (010)+ 1 2.3.3 NFA到DFA的变换（方法2） 子集构造法 1、DFA的一个状态是NFA的一个状态集合 2、读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk，则 DFA到达状态{s1, s2, …, sk} 1 2 a 开始 0 a b b {0} {0, 1} a 2.3 有 限 自 动 机 2.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 b {0} {0, 1} a b 2.3 有 限 自 动 机 2.3.3 NFA到DFA的变换 子集构造法 1、DFA的一个状态是NFA的一个状态集合 2、读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk，则 DFA到达状态{s1, s2, …, sk} 1 2 a 开始 0