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