编译原理第三章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,教学进度,计算机科学与工程系,第三章 词法分析与有穷自动机,词法分析器的,功能与输出,单词符号的两种定义方式,正规表达式与有穷自动机,正规文法与有穷自动机,词法分析器的设计,词法分析程序自动构造工具,LEX,简介,词法分析：对字符串表示的源程序进行从左到右的扫描和分解，根据语言的词法规则识别出一个个具有独立意义的单词符号。,3.1,词法分析器的功能,通常将词法分析程序设计为语法分析程序的子程序,源程序,词法分析器,语法分析器,单词符号,取下一个单词符号,(1),词法分析作为一个独立的阶段；,(2),与语法分析组织成一遍，作为语法分析的子程序,词法,分析,语法分析,语义分析和,中间代码生成,源程序,中间代码,符 号 表 管 理,错 误 的 诊 查 处 理,一、 语言的单词符号,（,token,）,具有独立意义的最小语法单位。,3.2,单词符号及输出单词的形式,关键字,标识符,常量,运算符,界符,：基本字 保留字,：表示各种名字,：常数,：,+ - * / ,：, ; : ( ),3.2.2,单词的输出形式：,（单词种别，单词自身的值）,3.2,单词符号及输出单词的形式,1,、单词种别,单词种别编码：整数码,一符一种、一类一种,2,、单词自身的值,标识符自身值的表示,常数自身值的表示,词法分析器的输出：,（单词种别，单词符号的属性值）,单词种别,提供给语法分析程序使用；单词自身的属性值提供给语义分析程序使用。,具体的分类设计以方便语法分析程序使用为原则。关键字可分成一类，也可以一个关键字分成一类。,常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。,while,(i!=j),if,(i,j),i,i-j,;,else,j=j,i;,词法分析器,例,while,，,(,，,i,，,!=,，,j,，,),，,if,，,(,，,i,，,j,), i, = , i, - , j, ;, ,else, j, =, j, -, i , ;,例如：程序段,if,(i,j),i=20;,经,词法分析器处理后，输出单词符号系列：,if,，, ,(,，, ,id,，,指向,i,的符号表入口的指针, ,，, ,id,，,指向,j,的符号表人口的指针,），, ,id,，,指向,i,的符号表入口的指针,=,，, ,con,，指向,20,的常量表入口的指针,；,，, ,2,，, ,29,，, ,10,，指向,i,的符号表入口的指针, 23,，, ,10,，指向,j,的符号表人口的指针,30,，, ,10,，指向,i,的符号表入口的指针,17,，, ,11,，指向,20,的常量表入口的指针,26,，, ,单词符号结构的描述方法：,正规文法（型文法）,(regular grammar),正规式（正规表达式）,(regular expression),3.3,单词符号的两种定义方式,例：标识符的定义,id let | id dig | id let,let ( let | dig )*,一、定义 设,=a,1,a,2,a,n,是字母表,正规表达式 正规表达式表达的语言（正规集）,1,.,，,， ,2,.,a,i, ,a,i,3,.,若有,r, s L( r ) ,L(s,),则有,( a ) r | s L( r ) ,L(s,),( b ),rs,L( r ),L(s,),( c ) ( r )* ( L( r )*,“,*,”,，连接，,“,”,运算左结合，优先级由高到低。,3.3.1,正规式与正规集,正规式 正规集,a b,a b,a|b,a,b,ab,ab,(,a|b,)* ,a,b,aa,ab,ba,bb,aaa,注意：,a,b,*,的任一子集，不能也认为是一个正规集。,如：,a,n,b,n,|n,1,例,3.2,=,a,b,c,aa,*bb*cc,*,例,3.3,例,3.1,字母表,=,a,b,R1=R2,正规式,R1,与,R2,等价,正规式的代数性质：,3.3.2,正规文法与正规式,对任何正规文法,G,，,存在定义同一语言的正规式,r,；,对任何正规式,r,，,存在生成同一语言的正规文法,G,。,（,等价关系，不是一一对应）,1.,正规文法到正规式的转换,将文法中的规则写成关于每个非终结符的正规式方程，得到一个方程组；,依照求解规则：,若,A=,A,|,，则解为,A=,*,；,若,A=,A,|,，则解为,A=,*,；,并使用正规式的代数性质，求文法开始符号的解。,例,3.4,例,3.5,例,3.6 P36-37,Z,=0(0|01),*,0,1.,正规文法到正规式的转换,将文法中的规则写成关于每个非终结符的正规式方程，得到一个方程组；,依照求解规则：,若,A=,A,|,，则解为,A=,*,；,若,A=,A,|,，则解为,A=,*,；,并使用正规式的代数性质，求文法开始符号的解。,例,3.4,例,3.5,例,3.6 P36-37,例,3.4,有正规文法,G,：,Z 0A,A 0A | 0B,B 1A |,例,3.6,有正规文法,G,：,Z U0 | V1,U Z1 | 1,V Z0 |,0,例,3.5,有正规文法,G,：,A,aB,|,bB,B,aC,| a | b,C,aB,A=(,a|b)(aa,),*,(,a|b,),Z=(10|01)(10|01),*,2.,正规式到正规文法的转换,字母表,上的,正规式,R,到等价的正规文法,G,：,令,V,T,=,；,令文法的开始符号,S =,R,；,对形如,A,ab,的规则转换为,A,aB,和,Bb,；,在新的文法中，将形如,A,a,*,b,的规则进一步转换为,A,aA,| b,；,不断利用和进行转换，直到每条规则的右部最多含有一个终结符号为止。,P37-38,例,3.8,R=(,a|b)(aa,),*,(,a|b,),例,3.9,R=,e(e|d,),*,3.4,正规式与有穷自动机,有穷自动机（,finite automata,）（,FA,）：具有离散输入和输出系统的一种抽象数学模型。,DFA NFA,正规式,R,与,FA M,是等价的：,(1),对任何正规式,R,都存在一个,FA M,使得,L(M)=L(R);,(2),对任何,FA M,都存在一个正规式,R,使得,L(R)=L(M),3.4.1,确定有穷自动机（,DFA,）,一个,DFA M,是一个五元式,M=,（,Q,，,，,，,S,，,F,）,其中，,Q,是有限状态集，,是输入字符的字母表，,是,Q,到,Q,的单值部分映射（即状态转换）,(q,i,a,)=,q,j,，,SQ,是唯一初态，,F,是终态集（可空）,例,3.10,设,DFA M=(q0,q1,q2,a,b,f,q0,，,q2,）,f(q1,a)=q1 f(q1,b)=q1,f(q2,a)=q2 f(q2,b)=q1,f(q0,a)=q1 f(q0,b)=q2,一个,DFA,可用一个,状态转换矩阵,表示,行表示状态，列表示输入字符，矩阵元素表示,(q,i,a,),的值。,一个,DFA,也可用一个,状态转换图,表示。,所以,一个有三种表示方法：,（,1,）转换函数；,（,2,）状态转换矩阵；,（,3,）状态转换图。,例 设（,， , ，,， ，）,其中,（，,），,（，,）,3,（，,），,（，,）,（，,），,（，,）,（，,），,（，,）,转换矩阵,3,b,0,1,2,a,a,a,a,b,b,b,3,状态转换图,易存储,从状态转换图看，从初态出发，沿任一条,路径到达接受状态，这条路径上的弧上的标,记符号连接起来构成的符号串被接受,(,识别,),。,DFA M,所能识别的字的全体即,L(M),。,字集,V,是正规的,iff,V=L,（,M,）,0,1,2,a,a,a,a,b,b,b,3,b,例：,DFA,，,接受,0,和,1,的个数都是偶数个的二进制串,3,1,2,0,1,1,1,1,0,0,0,0,开始,偶,0,偶,1,奇,0,奇,1,奇,0,偶,1,偶,0,奇,1,解释下列有限自动机分别识别什么语言？,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,3,4,5,a,a,a,a,a,2,一个,NFA M,是一个五元式,M=,（,Q,，,，,，,S,，,F,）,它包括：,状态集合,Q,输入符号集合,转换函数,:,Q,(,),P,(,Q,),S,是非空,开始状态,集,F,Q,是接受状态集合,例,3.11,P39,1,2,开始,a,0,a,b,b,识别语言,(,a,|,b,),*,ab,的,NFA,3.4.2,非确定有穷自动机（,NFA,）,1,2,开始,a,0,a,b,b,识别语言,(,a,|,b,),*,ab,的,NFA,输 入 符 号,a,b,0,0, 1,0,1,2,2,状 态,NFA,的转换表,例,识别,aa,*,|,bb,*,的,NFA,1,2,开始,a,0,a,b,b,3,4,注意：,NFA M,的状态转换图中可有,标记为,的边,。,DFA,是,NFA,的特例。,对于每一个,NFA M,存在一个,DFA M,使得,L(M) = L(M,),。,也就是说，每一个,NFA M,都可以转换成等价的,DFA M,。,NFA,DFA,正规式,正规文法,实现,最小化的,DFA,3.4.3,由正规表达式,R,构造,NFA,方法和步骤：,X,Y,R,R=, R=, R=a,R,为复合正规式？,X,Y,X,Y,X,Y,a,3.4.3,由正规表达式,R,构造,NFA,方法和步骤：,X,Y,R,R=, R=, R=a,R,为复合正规式？,A,B,r,1,r,2,A,B,r,1,|,r,2,A,B,r,1,*,A,B,r,1,C,r,2,r,1,A,B,r,2,C,A,B,r,1,例,3.12 3.13 P41,方法（子集法）,1,、改造,M,为,M,：,引进新的初态结点,X,、,终态结点,Y,；,对,M,的状态转换图实施分裂（替换）,2,、将,M,进一步变换为,DFA :,状态子集,T,的,闭包,_CLOSURE(T),定义状态集,T,a,=,_CLOSURE(J),从新初态,_CLOSURE(X),开始,计算状态转换矩阵；直到不再产生新的状态子集为止。,、换名,3.4.4 NFA,确定化为,DFA,例,3.14 3.15 P43-44,定义状态集,T,a,=,_CLOSURE(J),：,若状态子集,T=t,1,t,2,t,n,，则,(T,)=,_CLOSURE(J);,其中,J=,(,t,1,),(,t,2,),(,t,n,),i,：若,s,T,则,s,属于,_CLOSURE(T),；,ii,：若,s,T,则从,s,出发经过任意条,弧而能到达的状态,s,都属于,_CLOSURE(T),。,状态子集,T,的,闭包,_CLOSURE(T),：,NFA,到,DFA,的变换,子集构造法,DFA,的一个状态是,NFA,的一个状态集合,读了输入,a,1,a,2,a,n,后,，,NFA,能到达的所有状态：,s,1,s,2, ,s,k,，,则,DFA,到达状态,s,1,s,2, ,s,k,1,2,a,开始,0,a,b,b,NFA,到,DFA,的变换,子集构造法,DFA,的一个状态是,NFA,的一个状态集合,读了输入,a,1,a,2,a,n,后,，,NFA,能到达的所有状态：,s,1,s,2, ,s,k,，,则,DFA,到达状态,s,1,s,2, ,s,k,1,2,a,开始,0,a,b,b,0,0, 1,a,NFA,到,DFA,的变换,子集构造法,DFA,的一个状态是,NFA,的一个状态集合,读了输入,a,1,a,2,a,n,后,，,NFA,能到达的所有状态：,s,1,s,2, ,s,k,，,则,DFA,到达状态,s,1,s,2, ,s,k,1,2,a,开始,0,a,b,b,0,0, 1,a,b,NFA,到,DFA,的变换,子集构造法,DFA,的一个状态是,NFA,的一个状态集合,读了输入,a,1,a,2,a,n,后,，,NFA,能到达的所有状态：,s,1,s,2, ,s,k,，,则,DFA,到达状态,s,1,s,2, ,s,k,1,2,a,开始,0,a,b,b,0,0, 1,a,b,a,NFA,到,DFA,的变换,子集构造法,DFA,的一个状态是,NFA,的一个状态集合,读了输入,a,1,a,2,a,n,后,，,NFA,能到达的所有状态：,s,1,s,2, ,s,k,，,则,DFA,到达状态,s,1,s,2, ,s,k,1,2,a,开始,0,a,b,b,0,0, 1,a,b,a,0, 2,b,NFA,到,DFA,的变换,子集构造法,DFA,的一个状态是,NFA,的一个状态集合,读了输入,a,1,a,2,a,n,后,，,NFA,能到达的所有状态：,s,1,s,2, ,s,k,，,则,DFA,到达状态,s,1,s,2, ,s,k,1,2,a,开始,0,a,b,b,0,0, 1,a,b,a,0, 2,b,a,b,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,状态,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,状态,A,= 0, 1, 2, 4, 7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,B,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,C,= 1, 2, 4, 5, 6, 7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,C,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,C,= 1, 2, 4, 5, 6, 7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,C,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,C,= 1, 2, 4, 5, 6, 7,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,C,= 1, 2, 4, 5, 6, 7,D,= 1, 2, 4, 5, 6, 7, 9,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,D,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,C,= 1, 2, 4, 5, 6, 7,D,= 1, 2, 4, 5, 6, 7, 9,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,C,= 1, 2, 4, 5, 6, 7,D,= 1, 2, 4, 5, 6, 7, 9,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,C,状态,A,= 0, 1, 2, 4, 7,B,= 1, 2, 3, 4, 6, 7, 8,C,= 1, 2, 4, 5, 6, 7,D,= 1, 2, 4, 5, 6, 7, 9,有 限 自 动 机,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,C,状态,有 限 自 动 机,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,2,开始,a,0,a,b,b,a,b,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,识别语言,(,a,|,b,),*,ab,的,自动机,有 限 自 动 机,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,2,开始,a,0,a,b,b,a,b,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,识别语言,(,a,|,b,),*,ab,的,自动机,子集构造法不一定得到最简,DFA,结论：,NFA M,通过“子集法”可以确定化为,DFA M,，,它们接收语言的能力是等价的，通常不区分（确定化时除外,），,合称为有限自动机,(finite automata),（,FA,）。,3.4.5 DFA M,的化简,DFA M,的化简是指,:,寻找一个状态数比,M,少的,DFA M,，,使得,L(M)=L(M),化简了的,DFA,：,没有多余状态,；,没有两个状态是等价的。,3.4.5 DFA M,的化简,M,的状态,s,和,t,是等价的：,DFA M=,（,Q,，,，,，,S,0,，,F,），,s,t,Q,若对任何,a,*,(s,a),F,当且仅当,(t,a),F,如果状态,s,和,t,是不等价的，则称,s,和,t,是可区别的。,DFA M,的化简方法：,一个,DFA M,的状态最少化过程：将,M,的状态集分割成一些不相交的子集，任何不同的两子集中的状态都是可区别的，同一子集中的任何两状态都是等价的；最后，在每个子集中选一个状态作代表，消去其他状态，得到最少状态的等价,DFA M,。,例,3.16 3.17 P45-46,步骤：,将,DFA M,的状态集,Q,分划成两个子集：终态集和非终态集；,对每个子集,G,，如果面对某个输入符号得到的后继状态不属于同一个子集，则将,G,进一步分划；,重复,直到不再产生新分划；,在每个子集中选一个状态作代表，消去其他状态，得到最少状态的等价,DFA M,。,3.4.6,有穷自动机到正规式的转换,1,、改造,M,为,M,：引进新的初态结点,X,、,终态结点,Y,；,2,、对,M,的状态转换图实施替换，逐步消除结点，直至只剩下结点,X,、,Y,替换规则：,A,B,r,1,r,2,A,B,r,1,|,r,2,A,B,r,1,r,2,*,r,3,A,B,r,1,C,r,2,A,B,r,1,r,2,X,Y,R,P46,例,3.18,C,A,B,r,2,r,3,r,1,1,A,B,0,0,1,1*01*(01*01*)*,1,0,B,D,1,A,0,1,1,C,0,0,(0|1)*111(0|1)*,(00|11)*(01|10)(1(0(11)*0)*1|0(1(00)*1)*0)*1(0(11)*0)*|(00|11)*0,D,B,C,A,1,1,1,1,0,0,0,0,开始,偶,0,偶,1,奇,0,奇,1,奇,0,偶,1,偶,0,奇,1,3.5,正规文法与有穷自动机的等价性,对于正规文法,G,和有限自动机,M,如果,L(G)=L(M),则称,G,和,M,是,等价的,(equivalence),。,正规文法,G,和,M,的等价性是指：,(1),对每一个正规文法,G,都存在一个,FA M,使得,L(M)=L(G);,(2),对每一个,FA M,都存在一个,G,R,和,G,L,使得,L(M)=L(G,R,)=L(G,L,),3.5.1,右线性正规文法到有穷自动机的转换,对每一个正规文法,G,R,都存在一个,FA M,，使得,L(M)=L( G,R,);,已知文法,G,R,=(V,T,，,V,N,，,S,，,P),构造,NFA M=(,V,N,UD,V,T,S,，,D),对,A,a,有,(A,a,)=D,；,对,AaB,有,(A,a)=B,；,对,A,有,(A,)=D,P47-48,例,3.19,3.5.2,左线性正规文法到有穷自动机的转换,对每一个正规文法,G,L,都存在一个,FA M,，使得,L(M)=L( G,L,);,已知文法,G,L,=(V,T,，,V,N,，,S,，,P),构造,NFA M=(,V,N,Uq,0,V,T,q,0,，,S),对,A,a,有,(q,0,a)=A,；,对,ABa,有,(B,a,)=A,；,对,A,有,(q,0,)=A,P48,例,3.20,3.5.3-1,有穷自动机到正规文法,G,R,的转换,对每一个,FA M,都存在一个,G,R,和,G,L,使得,L(M)=L(G,R,)=L(G,L,),已知有穷自动机,FA M=(Q,q,0,，,Z),构造,G=(V,T,，,V,N,，,S,，,P),令,V,T,=,，,V,N,=,Q,，,S,=q,0,对,(A,a,)=B,且,B,不是终态，有,AaB,；,对,(A,a,)=B,且,B,是终态，有,AaB,和,B ,或,Aa,|,aB,；,若,q,0,也,是终态，则有规则,S,P49,例,3.21,3.22,3.5.3-2,有穷自动机到正规文法,G,L,的转换,对每一个,FA M,都存在一个,G,R,和,G,L,使得,L(M)=L(G,R,)=L(G,L,),已知,NFA M=,（,Q,，,，,，,q,0,，,f,）,构造文法,G,L,=(,，,Q- q,0,，,f,，,P),对,(A,a)=B,A,是,初态,则有,B,a;,否则,B ,Aa,若,f,也是初态，则有规则,f,结论,:,正规文法、正规式、,DFA,、,NFA,在识别（接收）语言的能力上是互相等价的。,例,0,，,1,上的串，该串看成二进制是,4,的倍 数。,正规式：,(0|1)*00 | 0,FA,：,正规文法：,3.6,词法分析程序的编写,设置,单词种别,和属性，用正规式编写词法规则,从单词的描述出发，逐步实现词法分析程序,手工方法,利用,LEX,自动生成,3.6,词法分析程序的编写,设置,单词种别,和属性，用正规式编写词法规则,从单词的描述出发，逐步实现词法分析程序,正规表达式,状态转换图,识别过程的实现算法,程序实现和测试,P50-53,0,2,l,1,非,d,非,l,l |d,17,16,13,9,4,d,3,非,d,d,5678,+ - * /,12,非,=,非,14,=,15,非,=,:,;,其它,实现：让每个状态对应一小段程序,词法分析,(lexical analysis),状态转换图,正规式与正规集,确定有限自动机,(DFA),非确定有限自动机,(NFA),NFA,确定化为,DFA,，,DFA,化简,正规式与正规文法的等价性,正规文法与,FA,的等价性,正规式与,FA,的等价性,词法分析器的自动生成工具：,LEX,用正规式描述单词符号,再从正规式产生识别这些单词的词法分析程序。,描述词法分析程序的,LEX,程序包括：一组正规式,/,动作,LEX,源程序,词法分析器,L,LEX,编译程序,词法分析器,L,输入串,单词符号串,1,、,LEX,源程序结构,辅助定义式,%,识别规则,%,用户子程序,正规定义式,:,d,1,r,1,d,2,r,2,.,.,.,d,i,r,i,d,i,为,名字,r,i,为,正规式,辅助定义式实例,标识符辅助定义式,:,Letter,A|B|Z|a|b|z,digit,0|1|2|3|4|5|6|7|8|9,identLetter(Letter|digit,)*,整常数辅助定义式,:,integerdigit digit*,一般实常数数辅助定义式,:,sign,+|-|,fraction,.integer,exponentE sign integer,numsign integer (fraction| )(exponent| ),LEX,源程序结构,辅助定义式,%,识别规则,%,用户子程序,识别规则,:,P,1,A,1,P,2,A,2,.,.,.,P,m,A,m,P,i,为词形,A,i,为,动作,分析器,L,只能识别具有词形,P,1,P,m,的单词符号,A,i,的基本成分是返回,P,i,的单词种别编码和属性值,+,return(10,-),-,return(11,-),* return(12,-),.,/ return(13,-),.,ident,return(9,),2,、,LEX,的实现原理,如何将一个,LEX,源程序改造为一个词法分析器,L,L,将像有限自动机,(FA),那样工作。,M,1,P,1,P2,P,m,M,2,M,m,X,二、,FA,的组装,一、对每个,Pi,构造一个相应的,NFA M,i,三、,NFA,转换为,DFA,四、构造词法分析程序,本章小结：,手工构造词法分析程序的方法：,NFA,DFA,正规式,正规文法,词法分析程序,最小化的,DFA,分裂法,转换,状态转换图,子集法,分划法,作业：,1,、有定义在,=0,，,1,上的正规集，它包含所有含相继的两个,0,或相继的两个,1,的二进制串，该正规集的正规式是,(0|1)*(00|11)(0|1)*,；,(1),构造识别该正规集且状态最少的确定有限自动机。（做法一：,NFA,、确定化和化简,给出每一步的结果；做法二：直接构造最小,DFA,，说明每个状态的含义。）,(2),写出等价的右线性正规文法。,(3),构造识别所有不含相继的两个,0,或相继的两个,1,的二进制串的,DFA,。,构造,DFA,练习：,1,、识别能被,3,整除的二进制串的,DFA,。,2,、识别能被,7,整除的二进制串的,DFA,。,3,、识别能被,3,整除的八进制串的,DFA,。,4,、含有相继的,111,的二进制串。,5,、不含相继的,111,的二进制串。,6,、识别不能被,3,整除的二进制串的,DFA,。,