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

《计算引论4语言的基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算引论第三章文法与语言第三章文法与语言3.1语言的基本概念3.2有限自动机3.3上下文无关语言3.4上下文无关语言识别算法3.1语言的基本概念字母表:符号的有限集合。例如二元字母表{0,1}字符串:假定是字符的有限集合，它的每一个元素称之为字符。由中字符相连而成的有限序列被称之为上的字符串（或称符号串）。3.1语言的基本概念空字符串:不含任何符号的字符串,用e表示字母表∑上的所有字符串,包括空串,记作∑*.字符串的长度即为序列的长度,对字符串w,长度表示为

2、w

3、.字符串w∑*可看成函数w:{1,…,

4、

5、w

6、}∑,w(j)的值即为w的第j位符号.3.1语言的基本概念字符串连接:假定是字符的有限集合,x,y是上的字符串,则把y的各个符号写在x的符号之后得到的字符串称为x与y的连接,记作x◦y或xy,形式地,w=x◦y,当且仅当

7、w

8、=

9、x

10、+

11、y

12、,w(j)=x(j)对j=1,…,

13、x

14、,及w(

15、x

16、+j)=y(j)对j=1,…,

17、y

18、.例:(1)S={a,b,c},x=ab,y=cba,那么,xy=abcba(2)01◦001=010013.1语言的基本概念设x是字符串,把x自身连接n次得到的字符串,

19、即z=xx…x(n个x),称为x的n次方幂,记作xn。注意：x0=exn=xxn-1=xn-1x(n1)x*=xn(n0),x+=xn(n1)例如：如果x=a,则x1=a,x2=aa,x3=aaa,如果x=ab,则x0=e,x3=ababab3.1语言的基本概念闭包：如果V是字符表上的字符串集合，那么，V的闭包定义为：V*=V0V1V2…正闭包：V+=V1V2…V+=V*-{e}例如：V={a,b}V*={e,a,b,aa,ab,bb,ba,aa,…}V+={a,b,aa,ab,ba,bb,

20、aaa,…}3.1语言的基本概念字符串集合的乘积设A,B是字符串的集合，则A,B的乘积定义为：AB={xy

21、xA,yB}例如:设A={aa,bb},B={cc,dd,ee}，则AB={aacc,aadd,aaee,bbcc,bbdd,bbee}A2={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语言的基本概念字符串的归纳定义:对字符串

22、w和自然数i,字符串wi可以定义为w0=e,空串wi+1=wi◦w,对每个i0字符串w的逆,记作wR,如reverseR=esrever3.1语言的基本概念字母表∑的任意字符串,即∑*的子集,称为语言,记为:L={w∑*

23、w具有性质P}若L1和L2为∑上的语言,则它们的连接为L=L1◦L2或L=L1L2,其中L={w∑*

24、w=x◦y且xL1及yL2}用L*表示所有由L中的字符串及空串连接的字符串集合.3.1语言的基本概念在计算理论中的一个核心问题是如何用有限的表示方式来表示一种语言.例,令L={w

25、{0,1}*

26、其中w中出现2~3个1,第一个和第二个不是连续的},可用单元素集及符号∪,◦及*表示为{0}*◦{1}◦{0}*◦{0}◦{1}◦{0}*◦(({1}◦{0}*)∪*)简写为L=0*10*010*(10*∪*)3.1语言的基本概念正则表达式：字母表∑*上的正则表达式为由∑∪{(,),,∪,*}组成的所有字符串,定义如下：和∑的每个成员都是正则表达式如果和为正则表达式,则()也是正则表达式如果和为正则表达式,则∪也是正则表达式若为正则表达式,则*也是正则表达式所有的

27、正则表达式都是按照1~4点形成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)

28、=(L(a)∪L(b))*{a}(3)=({a}∪{b})*{a}(1)={a,b}*{a}={w{a,b}*

29、w以a结束}3.1语言的基本概念正规语言:由∑上正则表达式描述的所有语言都称为正规语言,记作L=L()3.1语言的基本概念语言识别器(languagerecognitiondevice)：识别字符串w是否是语言L的成员的算法。例如,识别语言L={w{0,1}*

30、w不含有子串111}