编译原理_第3章_第1节_词法分析、DFA、NFA及其转换.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,I will greet this lecture with love in my heart.,源程序,目标程序,词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成,表格管理,错误检测,第三章 词法分析,主要内容,1.,介绍词法分析的,过程,2.,讨论词法分析器的,设计与实现,3.,介绍实现词法分析器的主要工具：,状态转换图,第三章 词法分析,3.1,词法分析器的任务,人们理解一篇文章（或程序）起码是先在,单词,级别上思考。,编译程序要分析和翻译源程序，也先要,区分,一个一个的,单词,。,词法分析程序的,任务,是：从左到右逐个字符对源程序扫描，产生一个单词序列，把作为字符串的源程序改造为单词符号串的中间程序。,词法分析程序又称,词法分析器或扫描器,。,除了识别单词的基本任务外，词法分析还可以完成,以下任务,：,（,1,）组织源程序的输入,（,2,）,删除,注释、空格及无用符号（如回车等）,（,3,）行、列,计数,（,4,）列表打印源程序,（,5,）,发现并定位,词法错误,（,6,）建立、查填,符号表,3.1.1,单词符号的表示,基本字：,也称关键字，如,C,语言中的,int,void,if,while,等；,标识符：,用来表示各种名字，如变量名、常量名、函数名等；,常数：,如,25,3.1415926,a,“,hello,”,TRUE,等；,算符：,如,+,=,等；,界符：,如逗号，分号，括号等。,基本字、运算符和界符一般确定；,标识符和常数的数量一般不加限制。,注：,（,1,）程序设计语言单词的分类纯属技术性问题，可以有不同的方法分类；,（,2,）除上述一般分类方法外，还有一字一类或一符一类等方法,单词的分类，如：,while(i=,“,),(1,指向,j,的符号表入口,),(5,“,),”,),(1,指向,i,的符号表入口,),(4,“,-,”,),(5,“,;,”,),数据类型,存储地址,int,3056,int,3060,例：,while(i=j)i-;,单词的表示：举例,3.1.2,词法分析器的结构,字符串形式的源程序,单词串形式的源程序,词法分析器,字符,词法分析器与语法分析器的联系,（,1,）词法分析作为单独的一遍,3.1.2,词法分析器的结构,将词法分析器分离的考虑,使整个编译程序的结构更简洁、清晰和条理化；,编译程序效率更高；,增强编译程序的可移植性。,(2),词法分析作为子程序,输入串,词法分析器,语法分析器,符号表,取下一单词,返回下一单词,词法分析器与语法分析器的联系,3.1.2,词法分析器的结构,扫描缓冲区,1.,预处理程序,：取消注解，剔除无用的空白、跳格、回车、换行等,2.,输入缓冲区,：源程序,输入缓冲区,3.1.2,词法分析器的结构,主要是为方便单词的识别工作：,（,1,）剔除无用的空白符、跳格符、回车符、换行符。,t,r,n,（,2,）剔除注释：,/*,*/,/,（,3,）合并空白符。,预处理程序,例：,int max(int x,int y)/,求,x,y,的最大值,int z;z=(x y?x:y);return z;,预处理后：,int max(int x,int y)int z;z=(xy?x:y);return z;,3.1.2,词法分析器的结构,预处理程序,3.1.2,词法分析器的结构,缓冲区的设计,起点指针：,用来指示正在扫描的单词的起点；,搜索指针：,用于向前搜索，寻找单词的结束；,缓冲区结构,扫描缓冲区：,从输入缓冲区输入固定长度的字符串到另一个缓冲区（扫描缓冲区），词法分析可以直接在此缓冲区中进行符号识别。扫描缓冲区的结构：,假设标识符和常数的最大长度为,256,缓冲区长度：,512,标识符起点,(500),搜索指示器,3.1.2,词法分析器的结构,标识符起点,(252),搜索指示器,缓冲区长度：,256,缓冲区长度：,256,：,设置左右两个缓冲区，当左缓冲区读完后，新读入的字符存入右缓冲区；反之，存放在左缓冲区；,缓冲区的设计,小结,词法分析器的任务；,单词符号的分类；,单词符号的表示；,词法分析预处理；,词法分析器的工作方式；,扫描缓冲区的双缓冲策略。,3.2.1,正规式与正规集,正规式（正规表达式）：,用以描述单词符号的工具，是说明单词的模式的一种重要的表示法,是定义正规集的工具。,一个正规式对应一个,正规集,正规,式和正规表达式,3.2.1,正规式与正规集,对字母表：,(1),和,都是上的正规式，它们所表示的正规集分别为,和,；,(2),a,，,a,是上的一个正规式，它所表示的正规集为,a,；,(3),假定,U,和,V,都是上的正规式，它们所表示的正规集分别记为,L(U),和,L(V),，那么,(U|V),、,(UV),和,(U)*,也是正规式，它们所对应的正规集分别为,L(U)L(V),、,L(U)L(V),和,(L(U)*,。,仅由,有限次,使用上述三步骤得到的表达式才是正规式，仅由这些正规式所表示的字集才是上的正规集。,例,3.1,令,=a,，,b,ba*,上所有以,b,为首，后跟任意多个,a,的,字符串,；,a(a|b)*,上所有以,a,为首的字符串；,(a|b)*(aa|bb)(a|b)*,上含两个连续,a,或两个连续,b,的,字符串,。,正规,式和正规表达式,3.2.1,正规式与正规集,例,3.1,令,=a,，,b,正规式,a,a|b,ab,(a|b)(a|b),a*,(a|b)*,(a|b)*(aa|bb)(a|b)*,正规集,a,a,b,ab,aa,ab,ba,bb,a,a,任意个,a,的串,a,b,aa,ab,所有由,a,和,b,组成的串,*上所有含有两个相继的,a,或两个相继的,b,组成的串,能被,5,整除的十进制整数的正则表达式,规则（,1,）：,表达式的头部为：,-,、,+,或,，表示整数的正、负,规则（,2,）,：十进制整数的尾部以,0,或者,5,结束,规则（,3,）,：整数的中部是任意,0-9,组成的数字串,3.2.1,正规式与正规集,(+|-|,),(0|1|9)*,(0|5),常用的正规式,整数：,(+|-|,),(0|1|9),(0|1|9),*,浮点数：,(+|-|,)(0|1|9),*,.(0|1|9)(0|1|9),*,标识符：,(a|z|A|Z|_)(a|z|A|Z|_|0|9),*,3.2.1,正规式与正规集,正规式的关系,交换律：,U|V=V|U,；,结合律：,U|(V|W)=(U|V)|W,；,U(VW)=(UV)W,；,分配律：,U(V|W)=UV|UW,；,(V|W)U=VU|WU,；,U=U=U,。,3.2.2,状态转换图,(TG),转换图是一张,有限方向图,；,结点表示,状态,，用圆圈表示；,状态之间用,有向弧,连接；,有向弧上的,标记,(,字符,),表示在射出结点所代表的状态下可能出现的输入符号或符号串；,一张转换图只包含,有限,个状态，且有一个,初态,，至少有一个,终态,；,一个状态转换图可用于识别,(,或接受,),一定的字符串，如,(a|b),*,(aa|bb)(a|b),*,。,3,0,1,2,b,a,a,b,b,a,a,b,状态转换图,3.2.2,状态转换图,(TG),状态转换图的作用：,（,1,）识别字符串是否为文法的句子（单词）,方法：,从文法的开始符号出发，按照与符号串预留部分中最左字符相匹配的原则游历状态图，直到符号串的末端为止。,如果这时恰好到达终止状态，则符号串为文法的句子，否则不是,3,0,1,2,b,a,a,b,b,a,a,b,如利用转换图判定字符串：,(1)ab,(2)aab,(3)aa,状态转换图的作用,3.2.2,状态转换图,(TG),状态转换图的作用：,（,2,）根据状态图可构造相应的语法分析程序。,画出状态转化图。,由正则文法或正则式构造状态转换图。,由状态转换图编写程序。,对于状态转换图中每一个状态构造一段代码，代码的功能是,从输入串中读入一个字符；,判断读入的字符与由此状态出发的哪条弧上的标记相匹配，便转至相匹配的那条弧所指向的状态。,均不匹配时便失败，即不能到达正常入口。,状态转换图的作用,3,0,1,2,b,a,a,b,b,a,a,b,3.2.3,确定有限自动机,(DFA),一个,DFA M,是一个五元组，,M=(K,f,S,Z):,(1)K,：状态集；,(2),：字母表；,(3)f,：从,K,到,K,的,单值部分映射,，即,f(k,i,a)=k,j,；,(4)SK,，是唯一的初态；,(5)Z,K,，是终态集。,0,1,a,2,a,0,1,a,3,当前状态和输入字符只能确定下一个状态,3.2.3,确定有限自动机,(DFA),DFA M=(K,f,S,Z):,(1)K=0,1,2,3;,(2)=a,b;,(3)f,：,f(0,a)=1,f(0,b)=2,f(1,a)=3,f(1,b)=2,f(2,a)=1,f(2,b)=3,f(3,a)=3,f(3,b)=3,(4)S=0,；,(5)Z,=3,。,a,b,0,1,2,1,3,2,2,1,3,3,3,3,3,0,1,2,b,a,a,b,b,a,a,b,例,1,：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成,(01),字符,串。,分析问题的状态空间：,0,：包含偶数个,0,偶数个,1,；,1,：包含偶数个,0,奇数个,1,；,2,：包含奇数个,0,偶数个,1,；,3,：包含奇数个,0,奇数个,1,。,不管串处于哪一种情况，只要再添加一个,0,或,1,，就会转换到另一种情况。,0,1,2,3,1,0,0,1,0,1,0,1,3.2.3,确定有限自动机,(DFA),例,2,：构造,DFA,，使其能接受,=0,1,上能被,4,整除的二进制数,分析问题的状态空间：,任意二进制数除以,4,，只有余数为,0,、,1,、,2,、,3,四种情况。,0,1,2,3,一个二进制数后面加,0,，相当于变为原来的,2,倍；后面加,1,，相当于变为原来的,2,倍加,1,。,若,x mod 4=0,则：,2x mod 4=0;,(2x+1)mod 4=1,0,1,若,x mod 4=1,则：,2x mod 4=2;,(2x+1)mod 4=3,0,1,若,x mod 4=2,则：,2x mod 4=0;,(2x+1)mod 4=1,0,1,若,x mod 4=3,则：,2x mod 4=2;,(2x+1)mod 4=3,0,1,3.2.3,确定有限自动机,(DFA),例,3,：一个人带着狼、山羊和白菜要从一条河左岸渡到右岸。有一条船，恰好能装下人和其它三件东西中的一件。用有限自动机找出渡河方案。,左岸存在的东西作为状态，初始为人、狼、羊、白菜都在左岸，接受状态为都不在左岸。,（人、狼、羊、白菜）,（人、狼、羊）,（人、狼、白菜）,（人、羊、白菜）,（人、狼）,（人、羊）,（人、白菜）,（狼、羊、白菜）,（狼、羊）,（狼、白菜）,（羊、白菜）,（人）,（狼）,（羊）,（白菜）,0,1,2,3,4,5,6,7,8,9,3.2.3,确定有限自动机,(DFA),0,人,狼,羊,白菜,1,人,狼,羊,2,人,狼,白菜,3,人,羊,白菜,4,人,羊,5,狼,白菜,6,狼,7,羊,8,白菜,9,用,G(x),表示人带,x,从左岸到右岸，,R(x),表示从人带,x,右岸回到左岸；,G,和,R,分别代表人自己去到右岸或回到左岸。,0,1,2,3,4,6,7,8,5,9,G(,羊,),G(,狼,),G(,羊,),G,G(,狼,),G(,白菜,),G(,羊,),G(,白菜,),G,G(,羊,),R,R(,羊,),R(,羊,),R(,白菜,),R,R(,狼,),R(,白菜,),R(,狼,),R(,羊,),R(,羊,),0,人,狼,羊,白菜,1,人,狼,羊,2,人,狼,白菜,3,人,羊,白菜,4,人,羊,5,狼,白菜,6,狼,7,羊,8,白菜,9,0,1,2,3,4,6,7,8,5,9,G(,羊,),G(,狼,),G(,羊,),G,G(,狼,),G(,白菜,),G(,羊,),G(,白菜,),G,G(,羊,),R,R(,羊,),R(,羊,),R(,白菜,),R,R(,狼,),R(,白菜,),R(,狼,),R(,羊,),R(,羊,),0,5283749,步骤：,G(,羊,),5(,狼,白菜,),R,2(,人,狼,白菜,),G(,狼,)8(,白菜,),R(,羊,)3(,人,羊,白菜,),(5)G(,狼,),7(,羊,),(6)R,4(,人,羊,),(7)G(,羊,)9(),问题：,任给一个正规式，如,(a|b),*,(aa|bb)(a|b),*,，如何构造其,DFA,？,0,a,b,1,2,3,4,a,a,b,b,5,a,b,(a|b)*(aa|bb)(a|b)*,0,a|b,3,a|b,1,2,aa,bb,0,(a|b)*(aa|bb)(a|b)*,1,a,b,0,0,1,2,0,1,3,1,2,3,2,4,5,3,4,5,4,5,5,5,5,5,0,a,b,1,2,3,4,a,a,b,b,5,a,b,NFA M=(0,1,2,3,4,5,a,b,f,0,5),f:f(0,a)=0,1,f(0,b)=0,1,f(1,a)=2,f(1,b)=3,f(2,a)=4,5,f(2,b)=,f(3,a)=,f(3,b)=4,5,f(4,a)=5,f(4,b)=5,f(5,a)=5,f(5,b)=5.,3.2.4,非确定有限自动机,(NFA),一个,NFA M,是一个五元组，,M=(K,f,S,Z):,(1)K,：状态集；,(2),：字母表；,(3)f,：从,K,*,到,K,的子集映像；,(4)S,K,，是初态集；,(5)Z,K,，是终态集。,DFA,和,NFA,在使用上各自的优点和缺点在哪里？,DFA,编程实现容易，但构造难,NFA,构造容易，但编程实现有回溯,能否找到一个从,NFA,到,DFA,的自动转换算法？,3.2.4,非确定有限自动机,(NFA),文法、正规式、,DFA(NFA),之间的关系,正则文法（,3,型文法）,正规式,DFA,NFA,3.2.5 NFA,确定化为,DFA,NFA M=(K,f,S,Z),，,DFA M,1,=(K,1,1,f,1,S,1,Z,1,),字母表,不必转换；,开始状态,：,DFA,中只有一个，,NFA,中有多个。,转换函数,：,DFA,是从,K,到,K,的映像,，而,NFA,是从,K,*,到,K,的子集,的映像。,区别：,K,到,K,的映像,K,*,到,K,的子集,3.2.5 NFA,确定化为,DFA,可以引入新的状态,X,，作为新的,NFA,的初始状态，然后从,X,向原,NFA,的每个初始状态引,弧。,0,1,a,2,b,X,3,0,1,a,2,b,3,一、多个初始状态向单个初始状态的转换：,二、,K,*,K,子集,K,K,K,*,K,子集,K,(),K,子集,K,K,3.2.5 NFA,确定化为,DFA,（,1,）,K,*,K,子集,K,(),K,子集,i,j,AB,i,j,A|B,i,j,A,*,i,j,A,k,B,i,j,A,B,i,j,k,A,3.2.5 NFA,确定化为,DFA,(a|b)*(aa|bb)(a|b)*,0,a|b,3,a|b,1,2,aa,bb,0,(a|b)*(aa|bb)(a|b)*,1,例：将下面的,TG,进行转换，使其弧上或为单个字符，或为,。,0,1,(a|b),*,(aa|bb)(a|b),*,0,2,3,1,(a|b),*,(a|b),*,aa|bb,0,2,3,1,a|b,4,bb,aa,a|b,5,0,2,3,1,4,5,b,a,b,a,6,7,a,b,b,a,K,*,K,子集,K,(),K,子集,K,K,3.2.5 NFA,确定化为,DFA,（,2,）,K,(),K,子集,K,K,0,1,a,3,0,A,a,0,1,3,4,I,_Closure(I),若,qI,，则,q_Closure(I),；,若,qI,，,q,=f(q,),则,q,_Closure(I),。,3.2.5 NFA,确定化为,DFA,0,1,a,2,3,a,0,A,a,若,I=S,1,S,2,S,k,则定义,move(I,a)=f(S,1,a)f(S,2,a),f(S,k,a),I,a,=_Closure(move(I,a);,0,1,3,a,4,a,5,I,（,2,）,K,(),K,子集,K,K,3.2.5 NFA,确定化为,DFA,0,1,a,2,3,a,4,5,b,b,0,A,a,4,5,b,b,B,b,0,A,a,I,I,a,I,b,0,1,2,3,1,2,3,4,5,4,5,假设,=a,1,a,k,开始状态为,X,，线性规划算法：,(1),构造一个有,k+1,列的表；,(2),首行首列为,_Closure(X);,(3),若某行第,1,列已经确定，则置该行,i+1,列为,I,ai,;,(4),若该行某项未在该表第一列出现，则填入该表后面空行的第一列；,(5),重复,(3)(4),，直到所有项均在第一列出现。,3.2.5 NFA,确定化为,DFA,例：构造正规式,(a|b)*(aa|bb)(a|b)*,的,DFA,Step1:,构造,NFA,0,a|b,3,a|b,1,2,aa,bb,3.2.6,构造正规式的,DFA,例：构造正规式,(a|b)*(aa|bb)(a|b)*,的,DFA,Step2:,使,NFA,初态和终态都唯一,0,a|b,3,a|b,1,2,aa,bb,X,Y,0,a|b,a|b,1,2,aa,bb,3,3.2.6,构造正规式的,DFA,例：构造正规式,(a|b)*(aa|bb)(a|b)*,的,DFA,Step3:,使,NFA,每条箭弧上或为单个字符,a,或为,X,2,5,Y,1,6,b,a,b,a,3,4,a,b,b,a,3.2.6,构造正规式的,DFA,例：构造正规式,(a|b)*(aa|bb)(a|b)*,的,DFA,Step4:,确定可合并状态,X,2,5,Y,1,6,b,a,b,a,3,4,a,b,b,a,I,I,a,I,b,X,1,2,X,2,1,2,Y,1,6,b,b,4,b,2,1,a,a,3,1,2,3,2,1,b,b,4,1,2,3,1,2,4,1,2,4,2,5,Y,1,6,a,a,3,a,1,2,3,5,6,Y,1,2,3,5,6,Y,2,1,b,b,4,1,2,4,2,1,a,a,3,1,2,3,Y,2,5,1,6,b,b,4,b,1,2,4,5,6,Y,1,2,4,5,6,Y,2,5,Y,1,6,a,a,3,a,a,1,2,3,5,6,Y,2,Y,1,6,b,b,4,b,1,2,4,6,Y,1,2,4,6,Y,2,Y,1,6,a,a,3,a,1,2,3,6,Y,1,2,3,6,Y,2,5,Y,1,6,b,b,4,b,b,1,2,4,5,6,Y,2,Y,1,6,a,a,3,a,1,2,3,6,Y,2,5,Y,1,6,b,b,4,b,b,1,2,4,5,6,Y,2,5,Y,1,6,a,a,3,a,a,1,2,3,5,6,Y,1,2,4,6,Y,3.2.6,构造正规式的,DFA,I,I,a,I,b,X,1,2,1,2,3,1,2,3,1,2,4,1,2,4,1,2,3,5,6,Y,1,2,3,5,6,Y,1,2,4,1,2,3,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,1,2,4,6,Y,1,2,3,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,S,a,b,0,X,1,2,0,1,1,2,3,1,2,3,1,2,3,0,6,1,1,1,1,1,1,2,1,2,4,1,2,4,1,2,4,2,2,2,2,2,2,1,2,3,5,6,Y,3,1,2,3,5,6,Y,1,2,3,5,6,Y,1,2,3,5,6,Y,3,3,3,3,3,3,3,3,4,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,4,5,6,Y,4,4,4,4,4,4,4,4,1,2,4,6,Y,5,1,2,4,6,Y,1,2,4,6,Y,5,5,5,5,5,5,1,2,3,6,Y,6,1,2,3,6,Y,1,2,3,6,Y,6,6,6,6,6,Step5:,合并状态,例：构造正规式,(a|b)*(aa|bb)(a|b)*,的,DFA,3.2.6,构造正规式的,DFA,S,a,b,0,1,1,1,2,2,2,3,3,3,3,4,4,4,4,5,5,5,6,6,6,0,1,2,1,2,3,1,2,4,0,2,1,a,b,3,3,5,4,4,6,4,5,6,6,3,5,4,b,6,a,0,2,1,a,b,3,b,2,1,a,2,1,a,4,b,3,b,2,1,a,2,1,a,4,b,4,b,6,a,3,a,5,b,3,a,5,b,4,5,6,b,a,4,5,6,b,a,3,5,6,a,b,b,3,5,6,a,例：构造正规式,(a|b)*(aa|bb)(a|b)*,的,DFA,Step6:,构造,DFA,0,2,1,a,b,4,b,6,a,0,2,1,a,b,3,b,2,1,a,2,1,a,4,b,3,a,5,b,4,5,6,b,a,3,5,6,a,b,X,1,2,1,2,3,1,2,4,1,2,3,5,6,Y,1,2,4,5,6,Y,1,2,4,6,Y,1,2,3,6,Y,0,X,1,2,1,1,2,3,2,1,2,4,3,1,2,3,5,6,Y,4,1,2,4,5,6,Y,5,1,2,4,6,Y,6,1,2,3,6,Y,3,4,5,6,例：构造正规式,(a|b)*(aa|bb)(a|b)*,的,DFA,Step7:,确定初态和终态,3.2.6,构造正规式的,DFA,总结：,NFA,确定化为,DFA,使初态和终态均,唯一,；,使,NFA,的每个箭弧上或为,单个,字符，或为,；,NFA,中，,=a,1,a,k,将,NFA,确定化：,（,1,）构造一张含有,k+1,列的表，置该表首行首列为,_Closure(X),；,（,2,）若某一行第一列已确定，则置第,i+1,列为,I,ai,，若该行某列未在该表第一列出现过，就将其加入到该表第一列最后一行；,（,3,）重复上述过程，直至出现在第,i+1,列上的所有状态子集均在第一列上出现过；,（,4,）将每个状态子集合并为一个状态，根据得到的状态转换矩阵构造,DFA,。,DFA,的初态为,首行首列,的状态，终态为那些含有原终态的状态子集。,与原来给出例题的比较,0,2,1,a,b,4,b,6,a,0,2,1,a,b,3,b,2,1,a,2,1,a,4,b,3,a,5,b,4,5,6,b,a,3,5,6,a,b,3,4,5,6,3,0,1,2,b,a,a,b,b,a,a,b,有四个终态,只有一个终态,1,、,DFA,是否可化简？,2,、如何化简？,3,、怎样才是最简,DFA,？,例：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成串。,Step1,：构造,NFA,正规式：,(,00|11|(01|10)(00|11)*(01|10),)*,0,1,(,00|11|(01|10)(00|11)*(01|10),)*,0,1,00|11|(01|10)(00|11)*(01|10),2,0,1,(01|10)(00|11)*(01|10),2,00,11,Step2,使每条弧上或为,，或为单个字符,0,1,(01|10)(00|11)*(01|10),2,00,11,0,1,2,(00|11)*,3,4,01|10,01|10,0,5,0,1,6,1,例：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成串。,0,1,2,(00|11)*,3,4,01|10,01|10,0,5,0,1,6,1,0,1,2,0,5,0,1,6,1,3,01,10,4,10,01,7,00|11,Step2,使每条弧上或为,，或为单个字符,例：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成串。,0,1,2,0,5,0,1,6,1,3,01,10,4,10,01,5,00|11,0,1,2,0,5,0,1,6,1,3,4,7,0,8,9,1,1,0,10,11,0,0,1,1,1,0,12,13,0,1,Step2,使每条弧上或为,，或为单个字符,Step3,使初态和终态都唯一,0,1,2,0,5,0,1,6,1,3,4,7,0,8,9,1,1,0,10,11,0,0,1,1,1,0,12,13,0,1,例：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成串。,Step4,寻找可合并状态,0,1,2,0,5,0,1,6,1,3,4,7,0,8,9,1,1,0,10,11,0,0,1,1,1,0,12,13,0,1,I,I,0,I,1,0,1,2,1,0,1,2,2,5,0,0,8,5,8,5,8,2,1,6,9,1,6,9,6,9,1,2,0,5,8,1,2,1,2,5,3,4,7,8,3,4,7,3,4,7,0,6,3,4,7,9,3,4,7,1,2,6,1,9,1,2,5,8,6,9,0,4,7,10,0,12,10,12,10,12,1,4,7,11,13,1,11,13,11,13,0,4,7,12,4,7,4,7,1,2,10,1,1,2,1,2,11,0,1,2,1,4,7,13,4,7,10,12,11,13,Step5,合并状态,I,I,0,I,1,0,1,2,5,8,5,8,6,9,6,9,1,2,1,2,3,4,7,3,4,7,3,4,7,1,2,5,8,6,9,10,12,10,12,11,13,11,13,4,7,4,7,1,2,1,2,4,7,10,12,11,13,0,1,2,0,3,4,7,I,I,0,I,1,0,0,5,8,1,5,8,5,8,1,1,1,1,1,1,6,9,2,6,9,6,9,2,2,2,2,2,2,1,2,3,1,2,1,2,1,2,1,2,3,3,3,3,3,3,3,3,3,3,3,4,7,4,3,4,7,4,4,4,4,4,4,10,12,5,10,12,10,12,5,5,5,5,5,5,11,13,6,11,13,11,13,6,6,6,6,6,6,4,7,7,4,7,4,7,7,7,7,7,7,7,例：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成串。,I,I,0,I,1,0,1,1,1,2,2,2,3,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,Step6,构造,DFA,1,2,3,2,3,4,1,3,4,4,5,6,5,6,7,3,5,7,3,6,7,0,1,2,0,1,2,0,1,3,4,0,1,0,1,0,1,5,6,0,1,7,0,1,0,1,0,1,例：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成串。,Step7,确定初态和终态：原终态为,1,0,1,5,6,0,1,0,1,2,0,1,3,4,0,1,0,1,7,0,1,0,1,0,1,0,1,2,5,8,6,9,1,2,3,4,7,10,12,11,13,4,7,0,1,2,0,5,8,1,6,9,2,1,2,3,3,4,7,4,10,12,5,11,13,6,4,7,7,0,3,例：构造,DFA,，使其能接受所有由偶数个,0,和偶数个,1,所组成串。,