第05讲-词法分析-IV.ppt

中国科大 小 结 DFA 确定的有限自动机（简称DFA) 数学形式定义 DFA是这样一个数学模型，包括 状态集合S 输入字母表? 转换函数 move: S ? ? ? S 唯一的初态s? S 终态集合F ? S NFA 不确定的有限自动机（简称NFA） 数学形式定义 DFA是这样一个数学模型，包括 状态集合S 输入字母表? 转换函数 move: S ? (??{?}) ? P(S) 唯一的初态s? S 终态集合F ? S NFA=DFA 理论依据 根据有限自动机理论，设L为一个有不确定的有限自动机接受的集合，则存在一个接受L的确定的有限自动机 怎样进行NFA到DFA的转化 子集构造法 本讲纲要 子集构造法 DFA化简 Lex 习题 NFA=DFA 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} NFA=DFA 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} NFA=DFA 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} NFA=DFA 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} NFA=DFA 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} NFA=DFA 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk， 则DFA到达状态{s1, s2, …, sk} 2.3 有 限 自 动 机 2.3 有 限 自 动 机 2.3 有 限 自 动 机 2.3 有 限 自 动 机 2.3 有 限 自 动 机 2.3 有 限 自 动 机 本讲纲要 子集构造法 DFA化简 Lex 习题 2.3 有 限 自 动 机 2.3.4 DFA的化简 通过算法构造的NFA，而后经过子集构造法得来的DFA通常不是最简的 如何判定一个DFA是不是最简，that’s a question DFA的化简 判断依据：状态的可区分性 状态的可区分性 存在串w，使得从状态s开始，对w进行状态转换，最终停在某个接受状态；而对于从t开始对w进行状态转换后，却停在某个非接受状态 2.3 有 限 自 动 机 可区别的状态 A和B是可区别的状态 A和C是不可区别的状态 DFA的化简 DFA化简的途径 根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的 依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系 2.3 有 限 自 动 机 化简时，DFA的状态转换函数必须是一个全函数 死状态 左图无须加死状态，右图加入死状态E。 2.3 有 限 自 动 机 方法 1. {A, B, C}, {D} move({A, B, C}, a} = {B} move({A, B, C}, b} = {C, D} 2. {A, C}, {B}, {D} move({A, C}, a} = {B} move({A, C}, b} = {C} 本讲纲要 子集构造法 DFA化简 补充 Lex 习题 词法模式识别过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab) 词法分析过程 一个串被DFA匹配的过程 (a|b)*ab 转换过程 m(0,abab) = m(m(0,a),bab) = m(1,bab