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