资源描述：
《文法和语言课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、文法和语言孙悦红文法和语言字母表和符号串文法推导句型和句子语言……形式语言自然语言（NaturalLanguage）歧义性（Ambiguity）冗余性（Redundancy）与字面意思的一致性形式语言（FormalLanguage）计算机的程序设计语言是毫无歧义的，字面和本意高度一致，能够完全通过对词法和语法的分析加以理解。形式语言20世纪50年代，语言学家NoamChomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。字母表和符号串任何一
2、种语言都是由该语言的基本符号所组成的符号串集合的子集。英语：26个字母和一些标点符号无符号整数：0、1、…、9“字母表”是元素的非空有穷集合。字母表中的每个元素称为“符号”，因此“字母表”也可称为“符号集”。{a，b，c，+，*}，{0，1}字母表和符号串“符号串”是由字母表上0个或多个符号所组成的任何有穷序列。a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb011,110011，所有二进制数注意ε也是字母表上的符号串，它由0个符号组成字母表和符号串符号串的长度：指符号串x中所含符号的个数，记为
3、
4、x
5、。
6、abc
7、=3，
8、abc+*abc
9、=8，而
10、ε
11、=0符号串相等：若x、y是字母表∑上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。当x=abbc，y=abbc时，则x=y当x=ab，y=ba时，则x≠y符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串。u、uni、university都是university的前缀符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串。ty、sity、university都是university的后缀符号串的子串：指从
12、符号串x的开头和末尾删除0或多个符号后得到的符号串。ver是university的子串符号串的前缀、后缀都是它的子串字母表和符号串符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串，则xy也是字母表∑上的符号串。x=ab，y=ba，那么xy=abba注意：连接没有交换率，即xy≠yx而对于空串ε有εx=xε=x字母表和符号串集合的乘积运算：令A、B为两个符号串集合，A和B的乘积AB定义为：AB={xy
13、x∈A，y∈B}。例如：A={a，b}B={c，d}则AB={ac，ad
14、，bc，bd}对于空集合有{ε}有：{ε}A=A{ε}=A字母表和符号串符号串的幂运算：若x是符号串，则x的幂运算定义为：x0=ε,x1=x,x2=xx,…,xn=xx…x=xxn-1=xn-1x,其中n>0例如：x=abc,x0=ε,x1=abc,x2=abcabc,…字母表和符号串集合的幂运算。设A为符号串集合，则A的幂运算定义为：A0={ε},A1=A,A2=AA……An=AA…A=AAn-1=An-1A其中n>0例如：A=={a，b}，则A0={ε}A1={a,b}A2={aa,ab,ba,bb}字母表和符号串集合的正闭包和集合的闭
15、包。设A为一个集合，则集合A的正闭包用A+表示，定义为：A+=A1∪A2∪….∪An∪…集合A的闭包用A*表示，定义为：A*=A0∪A+例如：A=={a，b}，则A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}一个集合的闭包比正闭包多个ε。文法在表示文法时，要说明语言的语法成分，句子中的符号以及语法结构。<句子>::=<主语><谓语><主语>::=<冠词><名词><冠词>::=<谓语>::=<动词><直接宾语><动词>::=<直接宾语>::=<冠
16、词><名词><名词>::=<名词>::=例如，能够描述句子“themonkeyatethebanana”的文法：文法著名的语言学家乔姆斯基在1956年对形式语言进行了定义。他把文法定义为四元组：G=（Vn，Vt，P，Z）其中：Vn为非终结符号集合；Vt为终结符号集合且Vt∈V（字母表）；P为有穷规则集合；Z识别符号，且Z∈Vn。文法G1=（Vn，Vt，P，Z）非终结符号集合:Vn={句子，主语，谓语，冠词，名词，动词，直接宾语}终结符号集合:Vt={the，ate，banana，monkey}识别符号Z：<句
17、子>例：文法<句子>→<主语><谓语><主语>→<冠词><名词><冠词>→the<谓语>→<动词><直接宾语><动词>→ate<直接宾语>→<冠词><名词><名词>→banana
