资源描述：
《编译原理词法2(NFA、DFA的确定化和化简).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3讲编译原理西北农林科技大学本科教程主讲教师：赵建邦第二章《词法分析》2.3-2.5节2.3正规表达式与有限自动机简介2.4正规表达式到优先自动机的构造2.5词法分析器的自动生成重点掌握有限自动机理论有限自动机的构造、确定化和化简本讲目标第二章词法分析2.1词法分析的设计方法2.2一个简单的词法分析器2.3正规表达式与有限自动机简介2.4正规表达式到有限自动机的构造2.5词法分析器的自动生成2.3.2：有限自动机：可以自动识别单词的机器有限自动机（FiniteAutomation）：FA是一个状态转换图，“有限”指的是状态有限。当前状
2、态读入一个字符后，和后继状态的转换有以下三种情形：(1)后继状态为自身(2)后继状态只有一个(3)后继状态有多个如果每次转换的后继状态是唯一的，则称它为确定有限自动机（DeterministicFA）如果每次转换的后继状态不是唯一的，则称它为非确定有限自动机（NondeterministicFA）2.3正规表达式与优先自动机简介2.3.2：有限自动机1、确定有限自动机（DFA）：DFA是一个五元组，Md＝(S,∑,f,s0,Z)，其中：(1)S是一个有限状态集合，它的每个元素称为一个状态(2)∑是一个有穷字母表，它的每个元素称为一个输入
3、字符f是一个从S×∑至S的单值映射，也叫状态转移函数s0∈S是唯一的初态是一个终态集2.3正规表达式与优先自动机简介2.3.2：有限自动机1、确定有限自动机（例2.4）：假定DFAMd=({s0,s1,s2}，{a,b},f,s0,{s2})，状态转移函数：f(s0,a)=s1f(s0,b)=s2f(s1,a)=s1f(s1,b)=s2f(s2,a)=s2f(s2,b)=s12.3正规表达式与优先自动机简介状态转换图：s2s0s1ababab状态转换矩阵：f∑abSs0s1s2s1s1s2s2s2s12.3.2：有限自动机2、非确定有限
4、自动机（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）：假定NFAMn=({s0,s1,s2},{a,b},f,{s0,s2},{s2})，状态转移函
5、数：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∑abSs0{s2}{s0,s2}s1Ф{s2}s2Ф{s1}状态转换图：s1s0s2babbb2.3.2：有限自动机（识别的语言）对于一个自动机FA而言，如果存在一条从初始状态到终止状态的通路，通路上有向边所识别的字符依次连接所得到的字符串为α,则称α可以为FA所接受或者α为FA所识别FA所能识别的字符串集为FA所识别的语言，记为L(M)FA的等价
6、：对于任意两个FAM和FAM’,如果L(M)=L(M’),则称M和M’等价对于任意一个NFAM，一定存在一个DFAM’与其等价2.3正规表达式与优先自动机简介2.3课堂例题例2.5接受与正规式(a
7、b)*abb相同的语言的DFA与NFA:DFA：s3s0s2aabbbaabs1NFA：s3s0s2aababs1DFA识别abbaabbabab无论成功或者失败只需要运行一次NFA识别abbaabbabab无论成功或者失败可能需要运行若干次第二章词法分析2.1词法分析的设计方法2.2一个简单的词法分析器2.3正规表达式与有限自动机简介2.4
8、正规表达式到有限自动机的构造2.5词法分析器的自动生成需要了解的等价性：1.如果R是字母表Σ上的一个正规式，则必然存在一个NFAM，使得L(M)=L(R);2.对于任意一个NFAM，一定存在一个DFAM’与其等价,即L(M)=L(M’);从正规式开始构造DFA的过程有以下几个步骤：1.由正规式构造NFA;2.由NFA构造与之等价的DFA（确定化）3.DFA的化简2.4正规表达式到有限自动机的构造（重点）2.4.1：由正规式构造等价的NFA1、对于给定的正规式R，将其表示成称为“拓广转换图”其中X为初始状态，Y为终止状态2、对正规式中的三
9、种运算，分别采用如下的对应转换规则2.4正规表达式到有限自动机的构造YXRsir1
10、r2sjsir1sjr2sir1r2sjsir1skr2sjsisjr1*siskεsjεr12.4正规表达式到有限自动机
