sun编译原理第3章词法分析与有穷自动机(第5-8讲).ppt

*,信息学院 孙丽云,*,第,3,章 词法分析与有穷自动机,3.1,词法分析程序的功能,所谓,词法,，即构成词的规则。,词法分析的,任务,是对字符串表示的源程序从左到右进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号。,词法分析是编译过程中的一个阶段，在语法分析前进行，可以作为单独的一遍，将源程序转换成,单词符号序列,供下一遍使用。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序获得当前记号，供语法分析使用。,1/31/2026,1,信息学院 孙丽云,3.2,单词符号及输出单词的形式,源程序,词法分析程序,单词符号,单词符号,是语言中具有独立意义的最小单位，包括保留字、标识符、常量、运算符和界符等。,词法分析程序输出的单词符号通常表示成如下的二元式：,（单词种别，单词自身的值）,1/31/2026,2,信息学院 孙丽云,正规式与正规集,3.3,语言单词符号的两种定义方式,多数程序设计语言的单词符号都能用,正规文法,或,正规式,来定义。,设有字母表,=,a1,，,a2,，,，,an,，在字母表上的正,规式和它所表示的正规集可用如下规则定义,：,（,1,）,是,上的正规式，它所表示的正规集是,，即空集,（,2,）,是,上的正规式，它所表示的正规集是,（,3,）,ai,是,上的正规式，它所表示的正规集由单个符号,ai,组成，即,ai,1/31/2026,3,信息学院 孙丽云,正规式与正规集,（,4,）如果,e1,和,e2,都是,上的正规式，它们所表示的正规集分别为,L(e1),和,L(e2),，则,e1|e2,是,上的一个正规式，它所表示的正规集为,L(e1|,e2,),=,L(e1),L(e2),e1e2,是,上的一个正规式，它所表示的正规集为,L(e1e2)=L(e1),L(e2),(e1)*,是,上的一个正规式，它所表示的正规集为,L(e1)*),=L(e1)*,正规式,描述了单词符号的构成规则，,正规集,是正规式能描述的所有的单词的集合。,1/31/2026,4,信息学院 孙丽云,设有字母表,=,a,b,根据正规式和正规集的定义有：,例,3.1,（,1,）,a,和,b,是正规式，相应正规集为,L(a,)=,a,（,2,）,a|b,是,正规式，相应正规集为,L(a|b,)=,a,b,（,3,）,ab,是,正规式，相应正规集为,L(ab,)=,ab,（,4,）,(,a|b,),*,是正规式，相应正规集为,L(a|b,)*),=,a,b,*,=,a,b,ab,ba,（,5,）,ba,*,是,正规式，相应正规集为,L(ba,*,),=,b,ba,baa,baaa,（,6,）,(,a|b,),*,(,aa|bb)(a|b,),*,是,正规式，相应正规集为,L,=,a,b,*,aa,bba,b,*,练习：,若,S=,a|bb,，则,L(a|bb,),*,)=,？,1/31/2026,5,信息学院 孙丽云,正规式中运算的优先级,括号优先，,*,次之，,（连接）再次之，,|,最后,例：,a|bc,*,a|(b(c,*),ab|c,*d (,ab)|(c,*)d),L(a|bc,*,)=,L(a)L(bc,*,),=,L(a)L(b)L(c,*,),=,L(a)L(b)(L(c,),*,=,ab,c,cc,ccc,=,a,b,bc,bcc,bccc,正规式与正规集举例,思考：,L(ab|c,*,d)=,？,1/31/2026,6,信息学院 孙丽云,设,A,B,C,均为正规式,则正规式有如下性质,:,A|B =B|A(,交换律,),A|(B|C)=(A|B)|C(,结合律,),A(BC)=(AB)C(,结合律,),A(B|C)=AB|AC(,分配律,),(A|B)C=AC|BC(,分配律,),A|A,=A,A,*,=AA,*,|=A|A,*,=(,A|,),*,(A,*,),*,=A,*,正规式的性质,1/31/2026,7,信息学院 孙丽云,正规文法与正规式,正规文法与正规式都是描述正规集的工具。对任意,一个正规文法，存在定义同一语言的正规式；反之，对每个正规式存在一个生成同一语言的正规文法。,3,型（正规文法）：,(,左线性,),P,：,U,t,或,U,Wt,其中,U,、,WN tT,(,右线性,),P,：,U,t,或,U,tW,其中,U,、,WN tT,1/31/2026,8,信息学院 孙丽云,正规文法到正规式的转换,(1),将正规文法中的每个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。,(2),依照,求解规则,:,若,x=,x|,(,或,x=,x+,),，则解为,x=,*,;,若,x=,x|,(,或,x=,x+,),，则解为,x=,*,;,以及正规式的分配律、交换律和结合律求关于文法,开始符号的正规式方程组的解,.,这个解是关于该,文法开始符号,S,的一个正规式，显然,它表示了由该正规文法所描述的语言。,1/31/2026,9,信息学院 孙丽云,正规文法到正规式的转换举例,例,3.4,设有正规文法,G,：,Z,0A,A0A|0B,B1A|,试给出该文法生成语言的正规式。,解,(1),联立方程组（用,+,代替正规式中的,|,）,(2),依照求解规则求解,1/31/2026,10,信息学院 孙丽云,正规文法到正规式的转换举例,例,3.5,设有正规文法,G,：,A,aB,|,bB,BaC,|a|b,CaB,试给出该文法生成语言的正规式。,解,(1),联立方程组（用,+,代替正规式中的,|,）,(2),依照求解规则求解,练习,1/31/2026,11,信息学院 孙丽云,正规文法到正规式的转换举例,例,3.6,设有正规文法,G,：,Z,U0|V1,UZ1|1,VZ0|0,试给出该文法生成语言的正规式。,解,(1),联立方程组（用,+,代替正规式中的,|,）,(2),依照求解规则求解,P28 (9),1/31/2026,12,信息学院 孙丽云,正规式到正规文法的转换,字母表上的正规式到正规文法,G=(V,N,V,T,P,S),的,转换方法如下,:,(1),令,V,T,=;,(2),对任意正规式,R,选择一个非终结符,Z,生成规则,Z,R,并令,S=Z;,(3),若,a,和,b,都是正规式,对形如,Aab,的规则转换成,AaB,和,Bb,两规则,其中,B,是新增的非终结符,;,(4),在已转换的文法中,将形如,Aa,*,b,的规则进一步转换成,AaA|b,;,(5),不断利用规则,(3),和,(4),进行变换,直到每条规则最多含有一个终结符为止,.,1/31/2026,13,信息学院 孙丽云,正规式到正规文法的转换举例,例,3.8,将,R=(,a|b,)(,aa,)*(,a|b,),转换成相应的正规文法,.,例,3.9,将,R=,l(l|d,)*,转换成相应的正规文法,.,练习,1/31/2026,14,信息学院 孙丽云,3.4,正规式与有穷自动机,有穷自动机是词法的识别工具，它的功能是：寻找（匹配）符合正规式要求的字符串，根据正规式确定正规集。,有穷自动机是描述特定类型算法的数学模型，可分为确定性有穷自动机,(DFA),和非确定性有穷自动机,(NFA),。,1/31/2026,15,信息学院 孙丽云,确定有穷自动机（,DFA,）,数学定义（五元组形式）：严密；,状态转换表：面向编程。,状态转移图：直观；,DFA,有三种表示形式,1/31/2026,16,信息学院 孙丽云,结点代表状态,(state),，,用圆圈表示。,状态之间用箭头,(transition),连结，代表一个状态向另一个状态的转换。,一个有穷自动机,只包含有限个状态,(,即有限个结点,),，其中只有一个为初态,(start state),（一个有开始状态的箭头指向），至少一个为终态,(,接受状态,accepting state)(,双圈表示,),。,例：标识符的有穷自动机。,有穷自动机的状态转移图表示方法,1/31/2026,17,信息学院 孙丽云,1,2,3,letter,letter,digit,other,other,any,状态,状态转移,初始状态,接受状态,a,v,3,f,k,/0,a,s,+,6,7,/0,两字符串的识别过程：,有穷自动机的状态转移图表示方法,1/31/2026,18,信息学院 孙丽云,确定有穷自动机（,DFA,）,输入字母表,Q,有穷状态集,f:Q Q (,状态转换函数,),SQ,唯一的初始状态,Z,Q,终止（接受）状态集合,这里的字母表是问题固有的；状态集合是编写,DFA,时定义的，是用户所做的命名。,DFA M,是一个五元组（,Q,f,S,Z,）,确定性有穷自动机,(DFA),：下一状态由当前状态和当前输入字符唯一给出的自动机。（取决于,f,）,“确定”,即状态转移函数是单值函数,数学定义,1/31/2026,19,信息学院 孙丽云,确定有穷自动机（,DFA,）,例：,M=(Q,f,S,Z,),其中：,=,a,b,z,A,B,Z,0,1,9,Q=1,2,3,，,S=1,，,Z=2,，,f=,f=Q Q,是如下的函数：,f(1,a)=2,，,，,f(1,z)=2,f(1,A)=2,，,，,f(1,Z)=2,f(2,a)=2,，,，,f(2,z)=2,f(2,A)=2,，,，,f(2,Z)=2,f(2,0)=2f(2,9)=2,f(1,0)=3f(1,9)=3,f(3,a)=3f(3,z)=3,f(3,A)=3f(3,Z)=3,1,2,3,letter,letter,digit,other,other,any,1/31/2026,20,信息学院 孙丽云,例：,有,DFA M=(0,1,2,3,a,b,f,0,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,它所,对应的状态表如图：,一个,DFA,可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示,T(s,a),的,值，这个矩阵称,状态表（,状态转移矩阵）。,状态,a,b,接受,0,1,2,否,1,3,2,否,2,1,3,否,3,3,3,是,状态,输入字符,后继,状态,状态表,1/31/2026,21,信息学院 孙丽云,DFA,三种表示形式的转化,1/31/2026,22,信息学院 孙丽云,DFA,所识别的语言,给定,DFA M,，对于字符,c1,c2,cn,当以下条件成立时，称,M,接受由,c1,c2,cn,组成的字符串,c1c2,cn,：,存在状态序列,s0,s1,s2,sn,使得,s1=f(S,c1),s2=f(s1,c2),sn,=f(sn-1,cn),，且,sn,Z,。,例：判断,abbbba,是否是上页,DFA M,所定义的语言,由,DFA M,接受的语言,L(M),是所有,M,接受的字符串组成的集合。,1/31/2026,23,信息学院 孙丽云,非确定有穷自动机（,NFA,）,由,M,接受的语言,L(M),L(M),c,1,c,2,c,3,.,c,n,|,c,i,U,s,1,=T(s,0,c,1,),s,2,=T(s,1,c,2,),s,n,=T(s,n-1,c,n,),s,n,A.,“,非确定”,即状态转移函数是,多,值函数,:,输入字母表,Q:,有穷状态集,f:S x(,U,),(S),(,状态转换函数,),S,Q,初始状态集,Z,Q,终止状态集,NFA M,也,是一个五元组（,Q,f,S,Z,）,1/31/2026,24,信息学院 孙丽云,转换函数,T,初态,NFA M(S,T,S,0,F),S,(,U,),S,的子集,多值映射,S,0,S,非空初态,集,DFA M(S,T,s,0,F),SS,的元素,单值映射,s,0,S,唯一的初态,NFA,与,DFA,的区别：,1/31/2026,25,信息学院 孙丽云,判断下图是,DFA,还是,NFA,的状态转换图，并写出其他,2,种表示形式,1/31/2026,26,信息学院 孙丽云,由正规表达式,R,构造,NFA,(a),对于正规式,所构造,NFA:,x,y,(b),对于正规式,所构造,NFA:,x,y,(c),对于正规式,a,a,则,NFA:,x,y,a,1.,基本正规表达式,1/31/2026,27,信息学院 孙丽云,由正规表达式,R,构造,NFA,2,、若,r,s,为正规式：,1,2,3,r,s,s,r,1,3,rs,r|s,r*,例：构造与正规表达式,R=,ab,*,a(a|b,),*,等价的,NFA,。,1,r,3,2,1/31/2026,28,信息学院 孙丽云,为,R=,(,a|b,)*(,aa|bb,)(,a|b,)*,构造,NFA,使得,L(N)=L(R),课堂练习,课后作业,P55 3.1(1)(2),1/31/2026,29,信息学院 孙丽云,NFA,确定化为,DFA,的方法,非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的。,NFA M,DFA M,构造成一个,使得,L(M)=L(M),1/31/2026,30,信息学院 孙丽云,定义,1,：状态集合,I,的,-,闭包：,令,I,是一个状态集的子集，定义,-closure,（,I,）,为：,1,）若,sI,，则,s-closure,（,I,）；,2,）若,sI,，,则从,s,出发经过任意条,弧能够到达的任何状态都属于,-closure,（,I,）。,状态集,-closure,（,I,）,称为,I,的,-,闭包,为了使得,NFA,确定化，给出两个定义：,5,6,4,3,2,a,a,a,1,例：如图所示的状态图：,令,I=1,，求,-closure,（,I,）,=,？,解：根据定义：,-closure,（,I,）,=1,，,3,例：,若,I1=1,2,，则,-closure,（,I1,）,=1,2,3,6,1/31/2026,31,信息学院 孙丽云,J,是从状态子集,I,中的每个状态出发，经过标记为,a,的弧而达到的状态集合。,I,a,是状态子集,其元素为,J,中的状态，加上从,J,中每一个状态出发通过,弧到达的状态。,定义,2:,状态子集的构造：,sI,例：令,I=1,，求,I,a,=,?,I,a,=-closure(J),=-closure(T(1,，,a),）,=-closure(2,，,4,）,=2,，,4,，,6,5,6,4,3,2,a,a,a,1,令,I,是,NFA M,的状态集的一个子集,a,定义,:,I,a,=-closure(J),其中,J=T(s,a),1/31/2026,32,信息学院 孙丽云,例：有,NFA M,，求,DFA M,。,a,1,2,3,4,start,a,b,a,c,c,I,I,a,I,b,I,c,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,初态,I=-closure(1)=1,4,I,a,=-closure(T(1,a)T(4,a),=-closure(2,3,）,=-closure(2,3),=2,3,I,b,=-closure(T(1,b)T(4,b),=-closure(,）,=,I,c,=-closure(T(1,c)T(4,c),=,I=2,3,I,a,=2,I,b,=4,I,c,=3,4,DFA,的状态,P42,1/31/2026,33,信息学院 孙丽云,符号,状态,a,b,c,0,2,3,4,1,2,2,1,_,_,_,_,_,_,_,_,3,3,4,4,DFA M,状态表,将求得的状态转换矩阵重新编号,start,0,1,4,2,3,1,4,2,3,4,2,a,c,a,b,b,c,3,4,I,I,a,I,b,I,c,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,包含,NFA,终态的状态子集全都是,DFA,的终态。,1/31/2026,34,信息学院 孙丽云,DFA,的化简,自动机理论中的结论：,对于任一个,DFA M,，存在一个唯一的状态最少的等价的,DFA M,即：一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。,等价状态 状态,s,和,t,的等价条件是,:,1),状态,s,和,t,必须同时为可接受状态或非接受状态。,2),对于所有输入符号,状态,s,和,t,必须转换到等价的状态里。,确定等价状态通常采用,逆向思维,：不直接寻找相互等价的状态，而是先确定互不等价的状态，即“可区别的状态”。当所有的互不等价的状态都被确定之后，那些不符合不等价条件的状态就是相互等价的状态了。,1/31/2026,35,信息学院 孙丽云,例,:,将该,DFA,最小化,5,7,2,4,3,6,1,srart,a,a,a,a,a,a,a,b,b,b,b,b,b,b,状态集的划分,将所有,DFA,的终态与其它状态划分成两个子集,G1,G2;,分别从两个子集,G1,G2,中,寻找不等价状态进行分割。,“,分割法,”,：把一个,DFA(,不含多余状态,),的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的,.,1/31/2026,36,信息学院 孙丽云,解,:,(,一,),区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,5,6,7,3,7,4,1,4,2,a,b,1,2,3,4,6,3,7,3,1,5,4,6,2,3,1,区号,5,7,2,4,3,6,1,srart,a,a,a,a,a,a,a,b,b,b,b,b,b,b,将所有,DFA,的终态与其它状态划分成两个子集,区号,1,2,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,1/31/2026,37,信息学院 孙丽云,1,2,4,3,1,2,4,3,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,5,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,区号,区号,1,2,3,4,5,a,b,5,2,1,4,3,5,5,2,3,1,1,5,5,2,4,3,a,a,a,a,a,b,b,b,b,b,5,6,7,3,7,4,1,4,2,a,b,1,2,3,4,6,3,7,3,1,5,4,6,1,2,3,区号,将区号代替 状态号得,:,1/31/2026,38,信息学院 孙丽云,例：,试求与下图所示,NFA,等价的化简了的,DFA,。,0,0,5,3,1,1,2,4,0,1,1,0,1,0,1,0,1,0,1,1,(1),23,(2),34,(3),23,(2),235,(4),34,(3),34,(3),23,(2),345,(5),235,(4),235,(4),345,(5),345,(5),235,(4),345,(5),0,1,1,(1),23,(2),34,(3),23,(2),235,(4),34,(3),34,(3),23,(2),235,(4),235,(4),235,(4),235,(4),化简后的,DFA:,1/31/2026,39,信息学院 孙丽云,有一台自动售货机，接受,1,分和,2,分硬币，出售,3,分一块儿的硬糖。顾客每次向机器中投放,3,分的硬币，便可得到一块糖（注意：只给一块并且不找钱）。请为自动售货机编制程序使其能够正确售出货物。,（,1,）写出售货机售糖的正规表达式；,（,2,）构造识别上述正规式的最简,DFA,。,（,3,）将该,DFA,用代码实现。,设顾客投入,1,分硬币用,a,表示，,2,分硬币用,b,表示，则售货机售糖的正规表达式为：,a(a(a|b)|b)|b(a|b,),DFA,与代码（略）,简单应用举例：,1/31/2026,40,信息学院 孙丽云,例：,设计一个,DFA,，其,输入字母表是,0,1,，它能接受以,0,开始，以,1,结尾的所有序列。,解：（,1,）根据题意，得出相应的正规式：,0(0|1),*,1,（,2,）得状态转换图,(NFA),（,3,）,NFA,转换,DFA,(4)DFA,最小化,正规式到,DFA,例：构造与正规式,R=(a,*,|b,*,),b(ba,),*,等价的状态最少的,DFA,正规式到,DFA,课堂练习,比较正规式向,DFA,转换过程中,弧多少的差异！,b,7,2,3,8,6,1,4,5,b,b,a,a,1/31/2026,41,信息学院 孙丽云,0,3,2,1,4,start,a,b,a,b,a,b,b,b,a,a,练习：,M,如右，求相应的正规式。,有穷自动机到正规式的转换,P46,转换规则：,(1),添加结点，保证只有一个初态结点和一个终态结点；,(2),逐步消去中间结点。,例：,P47,图,3.19,1/31/2026,42,信息学院 孙丽云,(),消除,M,中的所有结点,a|b,x,0,2,4,y,aa,bb,a|b,a|b,x,0,y,aa(a|b,)*,bb(a|b)*,a|b,x,y,(a|b)*(,aa|bb)(a|b,)*,解,:,(),加,x,y,(,新的初态和终态,),x,0,3,4,1,2,y,a,a,b,a,b,a,b,a,b,b,1/31/2026,43,信息学院 孙丽云,1,5,5,2,4,3,a,a,a,a,a,b,b,b,b,b,课后思考题：,有穷自动机到正规式的转换,1/31/2026,44,信息学院 孙丽云,正规文法,NFA,正规式,1,2,3,4,5,6,DFA,最小化,正规文法、正规式是描述正规集的工具，有穷自动机是识别正规集的工具，它们可相互转化。,1/31/2026,45,信息学院 孙丽云,例,:,有文法,Gs,S,aA|a,A,aA|dA|a|d,求相应的正规式,复习,S=,a(a|d,)*(,a|d)|,),规则：若,x=,x|,(,或,x=,x+,),，则解为,x=*;,若,x=,x|,(,或,x=,x+,),，则解为,x=,*;,正规文法,正规式,1/31/2026,46,信息学院 孙丽云,转换规则：,（,1,）,Aab,转换成,AaB,和,Bb,两规则,其中,B,是新增的非终结符,;,（,2,）,Aa,*b,转换成,AaA|b,;,例,:,将,R=a(a|d)*,转换成相应的正规文法,解,:1)S,a(a|d)*,2)S,aA,A,(a|d)*,S,aA,A,(a|d)A|,S,aA,A,aA|dA|,正规式,正规文法,复习,1/31/2026,47,信息学院 孙丽云,3.5,正规文法与有穷自动机,有穷自动机,正规文法,1.,对转换函数,T(A,t,)=B,可写成一个产生式,:A,tB,2.,对可接受状态,Z,，增加一个产生式,:Z,3.,有穷自动机的初态对应于文法的开始符号,有穷自动机的字母表为文法的终结符号集。,A,B,t,a,A,B,C,D,start,a,a,b,b,b,b,例：,G=(,a,b,A,B,C,D,P,A,),其中,P:A,aB,A,bD,B,bC,C,aA,C,bD,C,D,aB,D,bD,D,1/31/2026,48,信息学院 孙丽云,右线性正规文法,有穷自动机,例,:,求与文法,GE,等价的,NFA,GE:E,aA|bB|,A,aB|bA,B,aE|bA|,E,Z,A,B,start,a,a,a,b,b,b,解：,1.,字母表与,G,的终结符号相同,.,2.,为,G,中的每个非终结符生成,M,的一个状态,G,的开始符号,S,是开始状态,S;,3.,增加一个新状态,Z,作为,NFA,的终态,4.,对,G,中的形如,A,tB,的产生式,其中,t,为终结符或,A,和,B,为非,终结符,构造,M,的一个转换函数,T(A,t,)=B,5.,对,G,中的形如,A,t,的产生式,构造,M,的一个转换函数,T(A,t,)=Z,算法：,1/31/2026,49,信息学院 孙丽云,左线性正规文法,有穷自动机,例,:,求与文法,GE,等价的,NFA,GE:A,A1|B1,B,B0|0,1.,字母表与,G,的终结符号相同；,2.,为,G,中的每个非终结符生成,M,的一个状态，,G,的开始符号,S,是终结状态,Z,；,3.,增加一个新状态,Q,作为,NFA,的初始状态；,4.,对,G,中的形如,A,Bt,的产生式,其中,t,为终结符或,A,和,B,为非,终结符,构造,M,的一个转换函数,T(B,t,)=A,5.,对,G,中的形如,A,t,的产生式,构造,M,的一个转换函数,T(Q,t,)=A,算法：,1/31/2026,50,信息学院 孙丽云,正规文法,正规式,NFA,DFA,最小化,A,B,t,A,tB,(2),对终态,Z,增加,Z,(1),右线性文法增加终态；,左线性文法增加初态,解方程组，若,x=,x+,，则,x=*;,Aab,转换成,AaB,和,Bb,Aa,*b,转换成,AaA|b,;,1/31/2026,51,信息学院 孙丽云,转换综合练习,A,5,E,B,D,C,a,a,a,a,a,b,b,b,b,b,练习,1,：将该有穷自动机转换成等价的正规文法,G,练习,2,：将下列正规文法,G,转换成等价的正规式,练习,2,的正规文法：,S,dA|eB,A,aA|b,B,bB|c,练习,3,：给出下列文法对应的最小的,DFA,S,aS,|,bA,|b,AaS,练习,4,：构造正规式,1(0|1)*101,相应的,DFA,。,1/31/2026,52,信息学院 孙丽云,主要内容,1,、,DFA,与,NFA,的,3,种表示形式及其主要区别；,2,、正规式与正规集、,正规文法与文法定义的语言、,有穷自动机及识别的语言的概念及三者之间的相互转换。,3.,词法分析程序的编写方法。,4.,部分自测题,1/31/2026,53,信息学院 孙丽云,第,3,章 结 束,作业,:,自测练习题,3,+,习题,3 3.5,1/31/2026,54,信息学院 孙丽云,