资源描述:
《计算引论4语言的基本概念》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、计算引论第三章文法与语言第三章文法与语言3.1语言的基本概念3.2有限自动机3.3上下文无关语言3.4上下文无关语言识别算法3.1语言的基本概念字母表:符号的有限集合。例如二元字母表{0,1}字符串:假定是字符的有限集合,它的每一个元素称之为字符。由中字符相连而成的有限序列被称之为上的字符串(或称符号串)。3.1语言的基本概念空字符串:不含任何符号的字符串,用e表示字母表∑上的所有字符串,包括空串,记作∑*.字符串的长度即为序列的长度,对字符串w,长度表示为
2、w
3、.字符串w∑*可看成函数w:
4、{1,…,
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自身连
19、接n次得到的字符串,即z=xx…x(n个x),称为x的n次方幂,记作xn。注意:x0=exn=xxn-1=xn-1x(n1)x*=xn(n0),x+=xn(n1)例如:如果x=a,则x1=a,x2=aa,x3=aaa,如果x=ab,则x0=e,x3=ababab3.1语言的基本概念闭包:如果V是字符表上的字符串集合,那么,V的闭包定义为:V*=V0V1V2…正闭包:V+=V1V2…V+=V*-{e}例如:V={a,b}V*={e,a,b,aa,ab,bb,ba,aa,…}V+={a
20、,b,aa,ab,ba,bb,aaa,…}3.1语言的基本概念字符串集合的乘积设A,B是字符串的集合,则A,B的乘积定义为:AB={xy
21、xA,yB}例如:设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,对每个i0字符串w的逆,记作wR,如reverseR=esrever3.1语言的基本概念字母表∑的任意字符串,即∑*的子集,称为语言,记为:L={w∑*
23、w具有性质P}若L1和L2为∑上的语言,则它们的连接为L=L1◦L2或L=L1L2,其中L={w∑*
24、w=x◦y且xL1及yL2}用L*表示所有由L中的字符串及空串连接的字符串集合.3.1语言的基本概念在计算理论中的一个核心问题是如
25、何用有限的表示方式来表示一种语言.例,令L={w{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)
28、(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}*
29、w以a结束}3.1语言的基本概念正规语言:由∑上正则表达式描述的所有语言都称为正规语言,记作L=L()3.1语言的基本概念语言识别器(languagerecognitiondevice):识别字符串w是否是语言L的成员的算法。例如,识别语言L={w{0,1}*
30、w不含有子串111}