计算引论4语言的基本概念

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算引论,第三章 文法与语言,第三章 文法与语言,3.1 语言的基本概念,3.2 有限自动机,3.3 上下文无关语言,3.4 上下文无关语言识别算法,3.1 语言的基本概念,字母表,:符号的有限集合。,例如二元字母表0,1,字符串,:假定,是字符的有限集合，它的每一个元素称之为字符。由,中字符相连而成的有限序列被称之为,上的字符串（或称符号串）。,3.1 语言的基本概念,空字符串,:不含任何符号的字符串,用e表示,字母表,上的所有字符串,包括空串,记作,*,.,字符串的长度即为序列的长度,对字符串w,长度表示为|w|.,字符串w,*,可看成函数w:1,|w|,w(j)的值即为w的第j位符号.,3.1 语言的基本概念,字符串连接,:,假定,是字符的有限集合,x,y,是,上的字符串,则把y的各个符号写在x的符号之后得到的字符串称为x与y的连接,记作x,y或xy,形式地,w=,x,y,当且仅当|w|=|x|+|y|,w(j)=x(j)对j=1,|x|,及w(|x|+j)=y(j)对j=1,|y|.,例:(1)S,=a,b,c,x=ab,y=cba,那么,xy=abcba,(2)01,001=01001,3.1 语言的基本概念,设,x,是字符串,把,x,自身连接,n,次得到的字符串,即,z=xx x(n,个,x),称为,x,的,n,次,方幂,记作,x,n,。,注意,：,x,0,=,e,x,n,=xx,n-1,=x,n-1,x(n,1),x,*,=x,n,(n,0),x,+,=x,n,(n,1),例如：如果x=a,则x,1,=a,x,2,=aa,x,3,=aaa,如果x=ab,则x,0,=,e,x,3,=ababab,3.1 语言的基本概念,闭包：如果,V,是字符表,上的字符串集合，那么，,V,的闭包,定义为：,V,*,=V,0,V,1,V,2,正闭包：V,+,=V,1,V,2,V,+,=V,*,-,e,例如：,V=a,b,V,*,=,e,a,b,aa,ab,bb,ba,aa,V,+,=a,b,aa,ab,ba,bb,aaa,3.1 语言的基本概念,字符串集合的乘积,设A,B是字符串的集合，则A,B的乘积定义为：,AB,=,x y|x,A,y,B,例如,:,设,A=aa,bb,B=cc,dd,ee,，则,AB=aacc,aadd,aaee,bbcc,bbdd,bbee,A,2,=aaaa,aabb,bbaa,bbbb,3.1 语言的基本概念,字符串v为w的,子串,当且仅当存在字符串x和y使得w=xvy,空串e为任何字符串的子串.,若对x有w=xv,则v是w的,后缀,;若对y有w=vy,则v是w的,前缀,.,3.1 语言的基本概念,字符串的归纳定义:对字符串w和自然数i,字符串w,i,可以定义为,w,0,=e,空串,w,i+1,=w,i,w,对每个i,0,字符串w的逆,记作w,R,如reverse,R,=esrever,3.1 语言的基本概念,字母表,的任意字符串,即,*,的子集,称为语言,记为:,L=w,*,|w具有性质P,若L,1,和L,2,为上的语言,则它们的连接为L=L,1,L,2,或L=L,1,L,2,其中,L=w,*,|w=x,y且xL,1,及yL,2,用L,*,表示所有由L中的字符串及空串连接的字符串集合.,3.1 语言的基本概念,在计算理论中的一个核心问题是如何用有限的表示方式来表示一种语言.,例,令L=w,0,1,*,|其中w中出现23个1,第一个和第二个不是连续的,可用单元素集及符号,及*,表示为,0,*,1,0,*,0,1,0,*,(1,0,*,),*,),简写为,L=0,*,10,*,010,*,(10,*,*,),3.1 语言的基本概念,正则表达式：字母表,*上的正则表达式为由(,),*组成的所有字符串,定义如下：,和的每个成员都是正则表达式,如果和为正则表达式,则,(),也是正则表达式,如果和为正则表达式,则也是正则表达式,若为正则表达式,则*也是正则表达式,所有的正则表达式都是按照,14,点形成,3.1 语言的基本概念,语言：若,为正则表达式,则,L,()为表示的语言,其中,L,为字符串到语言的函数,L,定义如下:,L,()=,L,(a)=a其中a,若和为正则表达式,则,L,()=,L,(),L,(),若和为正则表达式,则,L,()=,L,(),L,(),若为正则表达式,则,L,(*)=,L,()*,每个正则表达式都表示一个语言。,3.1 语言的基本概念,例,L,(,(a,b)*a),),=,L,(a,b)*),L,(a)(2),=,L,(,(a,b)*,),a(1),=,L,(,(a,b),),*a(4),=(,L,(a),L,(b)*a(3),=(a,b)*a(1),=a,b*a,=w,a,b*|w以a结束,3.1 语言的基本概念,正规语言:由,上,正则表达式,描述的所有语言都称为正规语言,记作,L,=,L,(,),3.1 语言的基本概念,语言识别器,(language recognition device)：识别字符串w是否是语言L的成员的算法。,例如,识别语言L=w,0,1,*,|w不含有子串111,识别：设置一个计数器,初值为0,从左到右依次读 取被识别的字符串中每个字符,遇到0的时候计数器清0,遇到1时计算器加1,如果计数器为3时停止,回答No,若整个字符串读完时计数器不为3,则回答Yes。,3.1 语言的基本概念,语言产生器,:说明一种语言的如何产生的。,例如,正则式(,b,bb)(a,ab,abb),*,可认为是产生语言成员的方式：,为了产生L的成员,先什么都不写,或写b或bb;然后反复写下a或ab或abb多次或0次;这样L的所有成员都能产生.,语言产生器不同于语言识别器,它不是用来回答问题的,但是对表达语言十分重要.,