资源描述：
《第二章 符号语言与形式文法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章符号语言与形式文法软件开发环境国家重点实验室1第二章符号语言与形式文法字母表、字符串及其集合符号语言及其运算性质形式文法及其派生语言形式文法的构成与等价形式文法的乔姆斯基体系字母表与字符串定义2.1字母表是一个非空有限集合，通常记作∑，其中元素称为字母表的字符。字母表及其字符特点：1、字母表具有非空性和有穷性；2、字符具有不可分性-整体性；3、字符具有可区分性-可辨认性。例：考察以下字母表：∑1={aa,ab,bb}：是字母表，其中，aa不可拆分∑2={a,a‘,b,b’}：是字母表，其中，a,‘不可拆分∑3={a,b,a}：不是字母表，
2、两个a无法区分3字母表与字符串定义2.2设∑1，∑2是两个字母表，∑1，∑2的乘积定义为∑1∑2={ab
3、a∈∑1∧b∈∑2}。例：1、{0,1}{a,b,c}={0a,0b,0c,1a,1b,1c};2、{a,b,c}{0,1}={a0,a1,b0,b1,0c,c1};3、{aa,ab,bb}{0,1}={aa0,aa1,ab0,ab1,bb0,bb1}显然，字母表的乘积不具有交换率。字母表与字符串定义2.3设∑是一个字母表，∑乘积的n次幂可递归定义为：∑0={ε};∑n=∑n-1∑,n≥1。其中，ε是长度为0的字符串（空字符）。注：{ε}与
4、空集Φ的区别：1、ε是一个字符，用于标识长度为0的字符串；2、{ε}≠Φ：{ε}是含有一个长度为0的字符串标记集合。字母表与字符串定义2.4设∑是一个字母表，∑的正闭包：∑+=∑∪∑2∪∑3∪….,∑的克林闭包：∑*=∑0∪∑∪∑2∪∑3∪….,例：1、{0,1}+={0,1,00,01,10,11,000,001,010,011,100,...};2、{0,1}*={ε,0,1,00,01,10,11,000,001,010,011,100,...};3、{a,b,c}*={ε,a,b,c,aa,ab,ac,ba,bb,bc,…,aaa,…}
5、字母表与字符串定义2.5设∑是一个字母表，∑*中的任一字符串x也叫做∑上的一个句子。例：1、{0,1}*={ε,0,1,00,01,10,11,000,001,010,011,100,...};2、{a,b,c}*={ε,a,b,c,aa,ab,ac,ba,bb,bc,…,aaa,…}字母表与字符串定义2.6：字符串的长度设∑是一个字母表，∀x∈∑*，字符串x中字符出现的总个数叫做该串的长度，记作
6、x
7、。例：
8、ab
9、=2,
10、aab
11、=3,
12、an
13、=n,
14、a0
15、=
16、ε
17、=0思考：
18、{ε}
19、=？
20、Φ
21、=？8字母表与字符串定义2.7：字符串相等设α和
22、β是任意两个字符串，则α=β当且仅当
23、α
24、=
25、β
26、，并且组成α的字符与组成β的字符依次对应相同。例：若α=ab，β=ab，则α=β；若α=ab，β=ba，则α≠β。字母表与字符串定义2.8：字符串的连接设α和β是∑*上任意的两个字符串，α和β的连接构成一个新句子，记作α·β（简记为αβ），该句子由串α后直接接串β组成。对于n≥0，字符串α的n次幂为：（1）α0=ε；（2）αn=αn-1α例：设∑={0,1},x=001,y=1101；1、x0=y0=ε;2、xy=0011101;3、x2=0010014、y4=1101110111011101,
27、字母表与字符串字符串连接性质：对于∑*上任意字符串x,y,z,连接运算具有以下性质：1、结合律：(xy)z=x(yz)。2、左消去律：xy=xz⇒y=z。3、右消去律：yx=zx⇒y=z。4、唯一分解性：存在唯一确定的a,a,…,a∈∑,使得12nx=aa…a。12n5、单位元素：εα=αε=α字母表与字符串定义2.9：字符串的前缀与后缀设∑是一个字母表，任意字符串x,y,z∈∑*，且x=yz，则称y是字符串x的前缀；如果z≠ε，则称y是x的真前缀。z是x的后缀；如果y≠ε，则称z是x的真后缀。ε是任意字符串的前缀、后缀、子串。例：求∑={a,
28、b}上句子abaabb的前缀、后缀、真前缀、真后缀？前缀：ε,a,ab,aba,abaa,abaab,abaabb真前缀：ε,a,ab,aba,abaa,abaab后缀：ε,b,bb,abb,aabb,baabb,abaabb真后缀：ε,b,bb,abb,aabb,baabb字母表与字符串定义2.10：字符串的逆设ω=aa?a是任意字符串，称字符串a?aa是ω的12nn21逆，记作ωT例：设ω=abcd，ωT=dcba若ω=ωT，则称ω为回文。例：字符串0110110和deed都是回文。13第二章形式文法字母表与字符串符号语言以及其性质形式文法
29、及其派生语言形式文法的构成与等价形式文法的乔姆斯基体系符号语言及其运算性质定义2.11：符号语言设∑是任意字母表，∀L⊆Σ*，L称为字母表∑上的一个语
