编译原理词法2(NFA、DFA的确定化和化简).ppt

第 3 讲 西北农林科技大学本科教程 主讲教师：赵建邦 第二章《词法分析》2.3-2.5节 2.3 正规表达式与有限自动机简介 2.4 正规表达式到优先自动机的构造 2.5 词法分析器的自动生成 重点掌握 有限自动机理论 有限自动机的构造、确定化和化简 本讲目标 第二章 词法分析 2.1 词法分析的设计方法 2.2 一个简单的词法分析器 2.3 正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造 2.5 词法分析器的自动生成 2.3.2：有限自动机：可以自动识别单词的机器 有限自动机（Finite Automation）： FA是一个状态转换图，“有限”指的是状态有限。当前状态读入一个字符后，和后继状态的转换有以下三种情形： (1)后继状态为自身 (2)后继状态只有一个 (3)后继状态有多个 如果每次转换的后继状态是唯一的，则称它为确定有限自动机（Deterministic FA） 如果每次转换的后继状态不是唯一的，则称它为非确定有限自动机（Nondeterministic FA） 2.3 正规表达式与优先自动机简介 2.3.2：有限自动机 1、确定有限自动机（DFA）： DFA是一个五元组，Md＝ (S, ∑, f, s0 , Z) ，其中： (1) S是一个有限状态集合，它的每个元素称为一个状态 (2) ∑是一个有穷字母表，它的每个元素称为一个输入字符 f是一个从S×∑至S的单值映射，也叫状态转移函数 s0∈S 是唯一的初态 是一个终态集 2.3 正规表达式与优先自动机简介 2.3.2：有限自动机 1、确定有限自动机（例2.4）： 假定DFA Md =({s0, s1, s2}，{a,b}, f , s0 ,{s2} )，状态转移函数： f(s0, a) = s1 f(s0, b) = s2 f(s1, a) = s1 f(s1, b) = s2 f(s2, a) = s2 f(s2, b) = s1 2.3 正规表达式与优先自动机简介 状态转换图： s2 s0 s1 a b a b a b 状态转换矩阵： f ∑ a b S s0 s1 s2 s1 s1 s2 s2 s2 s1 2.3.2：有限自动机 2、非确定有限自动机（NFA）： NFA是一个五元组，Md＝ (S, ∑, f, Q, Z) ，其中： (1) S是一个有限状态集合，它的每个元素称为一个状态 (2) ∑是一个有穷字母表，它的每个元素称为一个输入字符 (3) f是一个从S×∑*至S的多值映射，也叫状态转移函数 (4) Q∈S 是非空初态集 (5) 是一个终态集 NFA相比于DFA的特征： 若干个初始状态 (2) f多值映射 (3) 允许接收字和空字符ε 2.3 正规表达式与优先自动机简介 2.3.2：有限自动机 2、非确定有限自动机（例2.5）： 假定NFA Mn =({s0, s1, s2},{a,b}, f , {s0 ,s2},{s2})，状态转移函数： f(s0, a) ={s2 } f(s0, b) ={s0,s2 } f(s1, a) = Ф f(s1, b) ={s2 } f(s2, a) = Ф f(s2, b) ={ s1 } 2.3 正规表达式与优先自动机简介 状态转换矩阵： f ∑ a b S s0 {s2} {s0,s2} s1 Ф {s2} s2 Ф {s1} 状态转换图： s1 s0 s2 b a b b b 2.3.2：有限自动机（识别的语言） 对于一个自动机FA 而言，如果存在一条从初始状态到终止状态的通路，通路上有向边所识别的字符依次连接所得到的字符串为α, 则称α可以为FA 所接受或者α为FA 所识别 FA 所能识别的字符串集为FA 所识别的语言，记为L(M) FA的等价：对于任意两个FA M和 FA M’, 如果L(M)=L(M’), 则称M和M’等价 对于任意一个NFA M，一定存在一个DFA M’与其等价 2.3 正规表达式与优先自动机简介 2.3 课堂例题 例2.5 接受与正规式(a|b) *abb相同的语言的DFA与NFA: DFA： s3 s0 s2 a a b b b a a b s1 NFA： s3 s