第三章-正则语言课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理,Principles of Compiler,第三章 正则语言,第三章 正则语言,正则语言,(Regular Language),一种最简单的形式语言。,计算机程序设计语言的词法属于正则语言的范畴。,本章内容：正则语言的三种模型,有穷状态自动机,正则表达式,正则文法,3.1,有穷状态自动机,一个识别,= a, 1 ,中所有标识符的程序：,int,nStatus,= 0;,while,(,ch,=,getch,() ),if,(,nStatus,= 0 ),if,(,ch,= a ),nStatus,= 1;,else,return,ERROR;,else,if,(,ch,!= a &,ch,!= 1 ),return,ERROR;,return,0;,3.1,有穷状态自动机,识别算法可以用图形表示：,3.1,有穷状态自动机,有穷状态自动机,( Finite Automata ),一台只有一个变量的计算机。,变量的取值范围有限，变量的一个值称为该计算机的状态。,计算机从初始状态开始运行，从坐向右读入输入的字符。,每读一个字符，根据一定规则修改状态值。,如果输入结束，当前状态为接受状态，则接受输入的串；否则拒绝输入串。,3.1,有穷状态自动机,FA,的表示方法,-,状态图：,状态：用圆圈表示，圆圈中符号标识状态,迁移：用连接两个状态的箭头表示，箭头上的符号为迁移的激活符号,初始状态：无源的箭头标识初始状态,接受状态：用双圈表示接受状态,3.1,有穷状态自动机,FA,的表示方法,-,迁移表：,a,1,0,1,1,1,1,FA,的语法,一台,FA,M,= (,Q,q,0,F,),，其中：,Q,为一个非空有穷的状态集合；,为有穷的字母表,(,符号集,),；,：,Q, ,Q,为状态迁移函数；,q,0,Q,为初始状态；,F,Q,为接受状态集合。,3.1,有穷状态自动机,M,= (,Q,q,0,F,),，其中：,Q,= 0, 1 ,；,= a, 1 ,；,= (0, a), 1), (1, a), 1), (1, 1), 1),；,q,0,= 0,；,F,= 1 ,。,FA,的语义,( FA,与语言的关系,),FA,的运行：,给定一台,FA,M,= (,Q,q,0,F,),M,的一个运行是一个有穷的状态序列,=,s,0,s,1,s,n,，其中：,s,0,=,q,0,；,s,n,F,；,0,i,n,( ,a,(,(,s,i,a,) = s,i,+1,) ),。,例：,01,，,011,，,0111,都是图中自动机的运行。,FA,的语义,( FA,与语言的关系,),FA,接受（识别）的串：,给定一台,FA,M,= (,Q,q,0,F,),称一个串,=,a,1,a,2,a,n,被,M,接受（识别），如果,M,存在一个运行,=,s,0,s,1,s,n,，使得：,0,i,n,(,(,s,i,a,i,+1,) = s,i,+1,),。,如果串,不被,M,接受，则称,M,拒绝,。,FA,M,的语言,L,(,M,),为所有,M,接受的串的集合。,FA,的语义,( FA,与语言的关系,),例：,FA,与正则语言,定义：称,FA,M,识别语言,L,，如果,M,恰好接受,L,中的所有串。,定义：一个语言是正则的，当且仅当存在一台,FA,识别它。,3.2,正则语言的封闭性,正则语言在并运算下的封闭性,定理：如果,L,1,与,L,2,为正则语言，则,L,1,L,2,也是正则语言。,证明思路：构造一台,FA,恰好识别,L,1,L,2,。,语言的性质,语言是符号串的集合,补运算,封闭性,如果语言,A,为正则语言，那么,A,的补集也是正则语言,语言封闭性的意义,3.2.3,正则语言的补运算,全集为,*,，即所有可能的符号串的集合。,证明思路,由于,A,为正则语言所以存在一台,DFA M,恰好识别,A,根据,M,，构造一台,DFA M,，恰好识别,A,的补集,对任何一个符号串，如果,M,接受，则,M,拒绝,如果,M,拒绝，则,M,接受,证明,L,(M) = A,的补集,例：一个正则语言的补集,0,1,补自动机的构造,原始自动机,补自动机,证明,证明方法,引理,1,在,FA,的计算过程中，有的时候需要“猜测”的功能,例：证明正则语言在乘积运算下封闭,普通的,FA,无法“猜测”,需要一种机制能够同时计算所有的可能,-,非确定性,3.3,非确定性的有穷自动机,NFA( Nondeterministic Finite Automata ),DFA( Deterministic Finite Automata ),NFA,与,DFA,的区别,从,DFA,的每一个状态出发，对于字母表中的每一个符号，最多只有一条迁移，而,NFA,可以有多条。,NFA,允许“空转移”，也就是能够不读入任何符号就迁移到另外的状态。,3.3,非确定性的有穷自动机,3.3,非确定性的有穷自动机,对同样的符号有多条迁移,允许空转移,3.3,非确定性的有穷自动机,NFA,的计算方式,每当遇到多种选择的时候就分裂，并发计算这些选择。,当输入结束的时候，只要有一个分支接受，则接受。,例：,输入为,1011,一台,NFA,M,= (,Q,q,0,F,),，其中：,Q,为一个非空有穷的状态集合；,为有穷的字母表,(,符号集,),；,：,Q, , 2,Q,为状态迁移函数，其中,=,；,q,0,Q,为初始状态；,F,Q,为接受状态集合。,3.3.1 NFA,的形式定义,3.3.1 NFA,的形式定义,表格表示方法,0,1,q,1,q,1,q,1,q,2,q,2,q,3,q,3,q,3,q,4,q,4,q,4,q,4,NFA,的运行：,M,的一个运行是一个有穷的状态序列,=,s,0,s,1,s,n,，其中：,s,0,=,q,0,；,s,n,F,；,0,i,n,( ,a,(,s,i,+1,(,s,i,a,) ),。,3.3.2 NFA,的语言,NFA,接受的串：,称一个串,=,a,1,a,2,a,m,被,M,接受（识别），如果存在一个串,= a,1,a,2,a,n,，其中,a,1,a,2,a,n,，使得,= ,，,而且,M,存在一个运行,=,s,0,s,1,s,n,，使得：,0,i,n,(s,i,+1,(,s,i,a,i,+1,),。,如果串,不被,M,接受，则称,M,拒绝,。,例：,0111,可以写为,01,11,3.3.2 NFA,的语言,N,FA,M,的语言,L,(,M,),为所有,M,接受的串的集合。,3.3.2 NFA,的语言,定义：如果两台自动机识别相同的语言，则称这两台自动机等价。,定理：对于任意一台,NFA,，都存在等价的,DFA,。,证明思路：对任意的,NFA,，构造一台,DFA,，模拟,NFA,的运行，用,DFA,的一个状态去记录所有分支的状态。,3.3.3 NFA,与,DFA,的等价性,3.3.3 NFA,与,DFA,的等价性,例：,证明：首先不考虑空转移的情况,令,NFA,N,= (,Q,q,0,F,),构造,DFA M =,(,Q,q,0,F,),，其中,Q,= 2,Q,对所有,q,Q,，,a,，令,(,q,a,) = ,r,q,(,r,a,),q,0,= ,q,0,F,= ,q,Q | q,包含,N,的一个接受状态,3.3.3 NFA,与,DFA,的等价性,考虑空转移的情况,定义函数,-Closure,对,M,的一个状态,q,Q,，,-,Closure,(,q,),表示从,q,中的状态出发，只经过空转移能到达的所有状态的集合,改写转移函数：,(,q,a,) = ,q,Q,|,存在,r,q,，使得,q ,-,Closure,(,(,r,a,) ,。,改写起始状态,q,0,=,-Closure,(,q,0,),3.3.3 NFA,与,DFA,的等价性,子集法,构造状态集的幂集，作为,DFA,的状态集；,对,DFA,的每一个状态，构造由其出发的迁移。,造表法,( On-the-fly ),首先构造,DFA,的初始状态；,对于现有,DFA,的状态，构造由其出发的迁移，如果迁移的目标为新状态则构造一个新的状态。,3.3.4,从,NFA,到,DFA,的转换,例：,3.3.4,从,NFA,到,DFA,的转换,推论：,一个语言是正则的，当且仅当存在一台,NFA,识别它。,定理：,正则语言在并运算、乘积运算、闭包运算下封闭。,3.3.5,正则语言的封闭性,并运算,3.3.5,正则语言的封闭性,乘积运算,3.3.5,正则语言的封闭性,闭包运算,3.3.5,正则语言的封闭性,利用运算符来构造语言运算的表达式，从而得到复杂的语言。,如果这些运算符为正则运算，则称这样的表达式为正则表达式。,正则运算：并、乘积、闭包。,3.4,正则表达式,语法：归纳定义,称,R,为一个正则表达式，如果,R,为以下情况的一种：,a,，,a,R,1,|,R,2,，,R,1,R,2,，如果,R,1,与,R,2,都是正则表达式,R,1,R,2,，如果,R,1,与,R,2,都是正则表达式,R,1,*,，,如果,R,1,是正则表达式,3.4.1,正则表达式的定义,语义：归纳定义,如果,R,为一个正则表达式，那么,R,的语言,L,(,R,),可以归纳定义如下：,L,(,a,) = ,a,L,(,) = ,L,() = ,L,(,R,1,|,R,2,) =,L,(,R,1,) ,L,(,R,2,),L,(,R,1,R,2,) =,L,(,R,1,),L,(,R,2,),L,(,R,1,* ) =,L,(,R,1,)*,3.4.1,正则表达式的定义,R,1,|,R,2,=,R,2,|,R,1,(,R,1,R,2,) ,R,3,=,R,1, (,R,2,R,3,),(,R,1,R,2,),R,3,=,R,1,(,R,2,R,3,),R,1, (,R,2,R,3,) = (,R,1,R,2,),(,R,1,R,3,),3.4.2,正则表达式的性质,定理：一个语言是正则的，当且仅当存在一个正则表达式描述它。,引理,1,：如果一个语言可以用正则表达式描述，则它是正则语言。,引理,2,：如果一个语言是正则的，那么可以用正则表达式描述它。,3.4.3,正则表达式与,FA,的等价,引理,1,：如果一个语言可以用正则表达式描述，则它是正则语言。,证明思路：对任意一个正则表达式，都存在等价的,FA,。,证明方法：归纳法，按照正则运算的次数归纳,归纳基础：运算次数,n = 0,；,归纳假设：假设运算次数,n ,0,；,|,|,p,。,证明思路：,令,DFA,M,识别,L,，,p,为,M,的状态数。,的长度大于等于,p,，,对应的运行,=,s,0,s,1,s,m,，满足,m,p,，因此,中存在重复的状态。,3.7,附录：正则语言的泵引理,令,k,为使得,中状态发生重复的最小下标，,=,s,0,s,1,s,j,s,k,s,m,，,s,j,=,s,k,例：,L,1,= 0,n,1,n,|,n, 0 ,不是正则语言,证明：,假设,L,1,是正则语言，那么必然存在泵长度,p,选择串,= 0,p,1,p,，将,分为三段,，考虑以下情况：,只包含,0,：,m,中,0,比,1,多,只包含,1,：,m,中,1,比,0,多,包含,0,与,1,：,m,中,0,与,1,的次序混乱。,所以,0,p,1,p,不能分割，与假设矛盾，即证。,3.7,附录：正则语言的泵引理,