计算引论4文法与语言

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算引论,第三章 文法与语言,求解问题,与 识别语言,问题抽象为符号串的集合；,符号串称为句子，问题是句子的集合；,求解问题抽象为识别语言,。,问题提出,:,如何构造可以接受及产生一个语言的计算模型,?,语言识别器,:,对一个已经存在的字符串集合,如何判断它就是符合条件的语言,?,解决接受的问题。,语言产生器,:,怎样产生一个语言？解决产生的问题。,语言的识别问题：,要让计算机自动识别语言（自然语言或机器语言或程序设计语言），必须先用形式化的方法来表示语言。,文法能清晰描述语言的语法构成,。,文法能自动构造有效的语言识别器。,文法,G,定义为四元组,(V,T,S,P),，其中,V,是有限的非终极符集合；,T,是有限的终极符集合；,S,是开始符，,S,T,。必须在某个产生式的左边出现一次；,P,是产生式的集合，且具有下面的形式：,，其中，,(,V,T,),*,非终极符号表示语法概念（如主、谓、宾等）或语法范畴。,终极符号表示语言的基本符号，例如,26,个字母（大、小写）及标点符号等。,S,是非终极符中的一个语法概念，是最关心的语法概念。,P,是语法规则，例如：,句子,定义为,主语谓语宾语,或,句子,定义为,主语系词表语,称为产生式，即由,主语谓语宾语,可以产生,句子,产生式表示一条语法规则，,P,为产生式集合。,文法分类：,A,B,V,，,a,T,。对文法中的产生式,：,O,型文法,:,短语文法。,中,至少含一个非终极符。,1,型文法,:,上下文有关文法。它是,0,型文法的特例，要求,|,|,|,|(S,例外，,S,不得出现于产生式右部,),。,2,型文法,:,上下文无关文法。它是,1,型文法的特例，要求产生式左部是一个非终极符,:A,。,3,型文法,:,正则文法。它是,2,型文法的特例，要求产生式具有下面形式之一,:Aa,，,AaB,。,文法的乔姆斯基体系,正则文法,上下文无关文法,上下文有关文法,短语文法,相关定义,定义,(,字符串,),：设,A,是基本符号表（字母表），,A=a,1,a,2,a,n,，则,A,上字符串集合表示为：,A,*,=A,0,A,1,A,2,A,k,A,+,=A,1,A,2,A,k,其中：,A,i,是长度为,i,的字符串,。,A*=A,0,A,+,推导,：如果,A,是一个产生式，则对字符串,A,，有,A ,表示一步推导,(,用,A),。,+,:,表示通过一步或多步可推导出,*,:,表示通过,0,步或多步可推导出,句型：,如果有,S,*,，则称符号串,为相应文法的句型，其中,S,是文法的开始符。,句子：,如果,只包含终极符，则称,为相应文法的句子。,语言：,L(G)=u|S,+,u,u,T,*,。,文法,G,所定义的语言是其开始符所能推导的所有终极符号串,(,句子,),的集合。,例：某语言有文法,G,：字母数学标识符，尖括号指非终极符。终极符,T,：,0,1,2,9,a,b,z,A,B,Z,_,。,P,中的产生式有：,数字,0,数字,1,数字,9,字母,a,字母,b,字母,z,标识符可以形式化地表示为：,标识符,字母,标识符,标识符字母,标识符,标识符数字,例：,G=(A,B,C,S,a,b,P,S),其中：,P,中的产生式集合为：,S,AB ,S,BC,B,CC ,B,b,C,AB ,C,a,A,BA ,A,a,试证明给定串,baaba,T,*,，且,S,baaba,，,即,是否,可以由文法规则推导出该串,。,证明：因为,baaba,串中的每一个字符均属于,T,，故,baaba,T,*,S,BC,bC,bAB,baB,baCC,baCa,baABa,baaBa,baaba.,3.2,正则语言的识别,正则文法定义：,G(V,T,P,S),P,中的产生式形如,A,a,或,A,aB,aT,A,BV,。,右范式,：形如,A,aB,称为右范式，其中非终极符于终极符的右边。,左范式,：形如,A,Ba,称为左范式，其中非终极符于终极符的左边。,正则语言,正则文法,G,生成的语言：,L(G)=|T,*,且,S,+,正则语言的识别,对文法,S,，任给串,T,*,，,S,+,成立否。,识别步骤：,任给串,T,*,，,S,+,成立否。,任给串,，,中所有的元素是否为给定终极符集中的元素构成。,可否由非终极符中的,S,经过多步推导得到串,。,识别算法,：设：,=a,1,a,n,a,i,T,。,若,n=1,，问题等价于检查,S,a,1,P,？,若,n2,，则需要证明,S,a,1,B,1,+,a,1,a,2,a,n,，,问题变为：,B,1,+,a,2,a,n,是否成立。递推下去，,B,1,a,2,B,2,？,+,a,2,a,n,B,2,a,3,B,3,？,+,a,3,a,n,B,n-1,a,n,？,即检查上述表达式是否均在文法集合,P,中。,正则运算,：设,A,和,B,是两个正则语言，,并,：,A B,x|xA,或,x B,连接,：,A B=xy|xA,且,yB,星号*：,A,*,=x,1,x,k,|k0,且,x,i,A,i,定理,1,：,正则语言在正则运算下封闭。,即：,如果,A,和,B,是正则语言，则,A,B,AB,A,*,也是正则语言。,3.3,有限自动机,有限自动机的结构,a,b,a,b,a,b,a,b,有限控制器,q,0,q,5,q,4,q,3,q,1,q,2,输入带,读头,特点,:,以字符串作为输入,通过输入带传送字符串,;,除了提示输入的字符串是否接受外,没有任何其它的输出,;,它的固定中央处理器完全没有记忆功能,;,类似一个语言识别器,.,组成,:,输入带,:,放字符串的装置,有限控制器,:,含不同的内部状态,读头,原理,:,在一定的时间间隔内,自动机根据从输入带上读入的符号和当前的内部状态,进入一个新的状态,.,过程,:,读取一个符号后,读写头向右移动一个方格,读取下一个符号,有限控制器的内部状态发生改变,.,最终读写头到达输入串的尽头,.,自动机将根据它所处的状态来说明它是否接受读入的字符串,如果此时的状态正好是一个终止状态,则认为该字符串是可接受的,.,根据每次转换后的状态是否唯一,可将有限自动机分为,确定有限自动机,和,非确定有限自动机,。,确定有限自动机,DFA,:,为一个五元组,M=(Q,q,0,F),其中,Q,为状态的有限集合,为有限字母表,q,0,Q,为起始状态,F Q,为终止状态集,：,QQ,是转换函数,格局,:,机器的状态,(,有限控制器,读写头和输入带,),的表示方式,.,由当前状态和字符串未输入部分决定,属于,Q,*,。,例如：（,q,2,ababab,）,连续时刻的格局序列就是自动机在输入字符串上的,计算,(computation).,若自动机,M,的一个格局经过一步,(,读写头,),移动到达另一个格局,则称这两个格局之间有二元关系,M,.,例如,若,(q,w),和,(q,w),为,M,的格局,(q,w),M,(q,w)iff,对某,a,有,w=aw,及,(q,a)=q,此时称,(q,w),一步产生,(q,w).,*,M,：,M,的自反传递闭包,如,(q,w),*,M,(q,w),，表示,(q,w),经过多步,(,包括,0,步,),产生,(q,w).,字符串,w,*,被,M,=(Q,q,0,F),接受,当且仅当存在状态,qF,使得,(q,0,w),*,M,(q,).,所有由被,M,接受的字符串组成的集合即为,M,接受的语言,记为,L(M).,有限自动机的表示,：,状态图,状态表,例,令,M,为确定有限自动机,(Q,q,0,F),其中,Q=q,0,q,1,=a,b,F=q,0,为如右表所示,q,w,(q,w),q,0,a,q,0,q,0,b,q,1,q,1,a,q,1,q,1,b,q,0,a,状态图,状态用结点表示,用标有,a,的从,q,指向,q,的箭头表示,(q,a)=q,终止状态用双圆圈表示,起始状态用,表示,q,0,b,b,q,1,a,若输入为,aabba,M,的初始格局为,(q,0,aabba),则有,(q,0,aabba),M,(q,0,abba),M,(q,0,bba),M,(q,1,ba),M,(q,0,a),M,(q,0,),即,(q,0,aabba),*,M,(q,0,),因此,aabba,被,M,接受。,非确定有限自动机,NFA,:,为一个五元组,M=(Q,Q,0,F),其中,Q,为状态的有限集合,为有限字母表,Q,0,Q,为起始状态集,F Q,为终止状态集,:Q,(Q),是转换函数,例,NFA,q,0,q,1,q,2,q,3,0,1,0,1,1,0,1,定义：,对两台自动机,M1,，,M2,，如果,L(M1)=L(M2),，则称,M1,和,M2,等价。,定理,2,：,每一台非确定有限自动机都等价于某一台确定有限自动机。,定理,3,：,语言是正则的，当且仅当它可以被有限自动机接受。,正则语言的描述局限,不能描述配对或嵌套结构,例,BEGINEND,不能描述重复串,例,wcw|w,是由,a,和,b,组成的串结构,