NLP入门之形式语言与自动机学习(三)

在前边的文章中我们把简单的需要的基础知识简单的列举了一遍,包括简单的集合逻辑,还有图论以及一些的证明方法等等,接下来我们将要开始我们正式的关于形式语言的学习,所以这一篇文章,我们将说一下什么是语言,以及语言的一些分类规则—文法,话不多说,即将开始.

1:什么是语言?

关于什么是语言这个问题,大家可能会想,语言,我们每天说的汉语,英语,甚至我们计算机常用的编程语言不都是语言么?在当今的世界上,程序设计语言可能达到了几千种,他们的语言规则都千差万别,但是他们总体来看都是有一个共同的特点,都是由一个有限字母表上的字母的集合所组成的,也就是说我们是可以用一种统一的抽象方法来进行讨论,研究程序设计语言的.形式语言在之前我们提的定义中就是对程序设计语言的形式化描述,这里边我们就可以引申出两种重要的方向:

一:研究产生语言的形式规则—文法

二:识别语言的装置—机器

下边的这些文字讨论的就是这样的顺序和规则.

在这一篇文章中,我想和大家先了解下有关语言的术语,比如说字母表,字符串,语言,以及语言的运算规则等等,然后在此基础就引申出什么是文法,以及文法的分类等等.(这里边一些定义类的东西我就直接引用蒋宗礼老师书中的定义,定义类的东西不好自己定义,容易出错)

1:字符的有限集合称为字表,记为T

关于这条定理,我们可以可以这么理解,比如说26个英文字母,10个阿拉伯数字都可以构成不同的字母表,字母表作为一个集合,在理论上是可以是一个无限大的集合的,但是在实际应用上,总会有一些的规则,所以字母表的中的字符个数总是有限的.

2:由字表T中的字符构成的有限序称为字母表T上的字符(或句子)。

比如说现在有一个字母表T={a,b,c,d,.....0,1,2....9},现在随机拼出的acab001,bseg9282,这些都可以认为是字母表上T的字符串,只是这样没有什么意义罢了.

字符串中所包含字符的个数,称为字符串的长度。

比如上边的|acab001| = 7,|bseg9282| = 8,长度为0的字符串,称为空串,记为ε,空串中是没有任何字符的字符串,但是这也是有用的.

约定今后小写字母a,b,c,d表示单个字符;t,u,v,w,x,y,z表示字符;an表示n个a的字符。

3:字符串的运算

设w1和w2是字母表T上的字符,w1=a1a2…am,w2 =b1b2…bn,则w1w2 =a1a2…amb1b2…bn称为字符w1和w2的连接。

显然,字母表上的任意一个字符w与空串的连接还是w,即εw=wε =w

字符串w的逆,用w表示,w是字符串w的倒置。如,当w=b1b2…bk,则w=bk…b2b1。空ε的逆还是ε,即ε =ε。

设w1,w2,w3是字母表T上的字符,称w1是字符w1w2的前缀,w2是w1w2的后缀,且w2是字符串w1w2w3的。

举个例子:比如abcd,这样abc就可以看为是abcd的前缀和子串,d就可以看为abcd的子串和后缀.在这里,子串是一个特殊情况,他是属于任何字符串的前缀,后缀,以及子串.

4:T*是字母表T上的所有字符串和空集的集合,T+是字母表T上的所有字符串构成的集合,并有T+ =T* - {ε}。

5:字母表T上的语言L是T*的子集.

在这里应该注意,∅和{ε }是两个不同的意思,∅表示的是什么也没有,空句子也不会存在,{ε }表示的是只有一个空句子的集合.

比如:设字母表T是C语言中所用的全部符号的集合,那么语法正确的C语言程序也是C语言字母表上的语言.

根据语言的定义可以得到,语言其实就是一个集合,因此对于语言的运算就跟集合的运算一样,

并、交、补、差运算均可应用于对语言的运算。

6:语言的基本运算

1:两个语言L1和L2的积L1·L2(简记为L1L2),是由L1和L2中字符串的连接所构成的字符串的集合.

举例:

设字母表T={a,b},L1和L2是T上的语言,并有L1={a,b,ab},L2 ={bb,aab}

那么就有:

L1L2 = {abb,aaab,bbb,baab,abbb,abaab}

L2L1 = {bba,bbb,bbab,aaba,aabb,aabab}

上边的这个例子也隐藏了一点L1L2≠L2L1,这个跟矩阵当中的积运算不可交换是一个样子的.

2:语言L的幂可归纳定义如下:

L0 ={ε}

Ln=L·Ln- 1n≥1

接着上边的例子中的L1,L2,套用上边的定义:

L21 = {aa,ab,aab,ba,bb,bab,aba,abb,abab}

L22 = {bbbb,bbaab,aabbb,aabaab}

3:语L的闭包L*定义为L* =∪Ln(n≥ 0)

语L的正闭包L+定义为:L+ =∪Ln(n≥ 1)

显然,L+ =LL* =L*L,L* =L+∪{ε}。

举例:

设L={ba,bb},

则L* ={ba,bb}* = {ε,ba,bb,baba,babb,bbba,bbbb,…}

L+ ={ba,bb}+ = {ba,bb,baba,babb,bbba,bbbb,…}

二:文法

在上文中我们会发现,如果语言L是有限集合的话,那如果次数小有限集合的确可以用列举法来去解决这个问题,但是如果是无限的集合语言L,那么就不能再用列举法了,必须要寻找到一个更加简便的方法.

科学家们做了很多的探索:

探索方向1:是所谓“文法”的产生系统。它能够由定义的文法规则产生出语言的每个句子.

探索方向2:是用一个语言的识别系统。当一个字符串能够被一个语言的识别系统接受,则说这个字符串是该语言的一个句子,否则不属于该语言.

我们将会主要讨论探索方向1,第二种方法后来演变成了各种语言的识别器,以后我们可能会谈一谈,关于第一种方法,使用的主要是文法,那什么是文法?

所谓的文法,简单来说就是一个定义语言的数学模型.蒋老师的书中讲的是Chomsky的文法体系,Chomsky文法体系中间的任何一种文法必包含有:两个不同的有限符号集合,即非终结符号集合N和终结符号集合T;一个形式化规则的有限集合P,也称生成式集合;一个起始符S。其中,集合P中的生成式是用来产生语言的规则,则是仅由终结符组成的字符;同时这些字符串的产生必须从一个起始符S开始,不断使P中的生成式而导出来的。可见,文法的核心是生成式集合,它决定了语言中句子的产生。

2:语法的形式定义

1:法G是一个四元组,G=(N,T,P,S),其中(1)N终结符的有限集合;

(2)T是终结符的有限集合,且N∩T=∅;

(3)P是形式为α→β的成式有限集合,且a∈(N∪T)+,β∈(N∪T)*,且α少含一个非终结符号;

(4)S是起始符,且S∈N。

PS:在定义,成式α→β中,所用符号“→”的含义是“可被代替”。

比如说:设文法G=(N,T,P,S),其中,N={A,S},T={a},成式P如下:

S→a,S→aA,A→aS.

2:字符α是文法G的句型,当且仅当S*Gα,且

α∈(N∪T)*;w是G的,当且仅当S*w,且w∈T*。G

由文法G产生的语(记为L(G))是w|w∈T*且S*w,G

或者说,L(G)中的个字符,必是由终结符组成,并且是从起始符S推导出来的。

举例:

文法G=({A,S},{a},P,S),其中生成式P如下:S→a,S→aA,A→aS。

这样的话由文法G产生的语言L(G)有:

Sa a∈L(G),

SaA aaS aaa aaa∈L(G),

SaA aaS aaaA aaaaS aaaaa aaaaa∈L(G),

这样一直下去

将推导出的语言写成一般形式,则有

L(G)= {a2n+1}n≥0。

在推导序列S aA aaS aaaA aaaaS aaaaa中,S,aA,aaS,aaaA,aaaaS都是句型,aaaaa则是句子.

3:文法的分类:

1:前面定义的文法,属于Chomsky的文法体系,该体系对生成式的形式作一些规定,分为四类,因此文法也分为四种类型,即0型、1型、2型和3型文法,按生成式的不同介绍如下:

1 .0型、1型、2型和3型文法介绍

1型文法:

或者称为上下文有关文法。生成式的形式为α→β,其中,|a|<=|β|,并且α,β∈(N∪T)+.

举例:

设文法G=(N,T,P,S),其中N= {S,A,B},T= {a,b,c},

那么生成式如下:

S→aSAB,

aA→ab,

S→aAB,

bA→bb,

BA→AB,

bB→bc,

cB→cc

表明G是1型文法,因为每个生成式左部字符串度小于或等于右部字符串长度。

2型或称上下文无关法。生成式的形式为A→α,A∈N且α∈(N∪T)*。

例子:

设文法G=(N,T,P,S),其中N= {S,B,C},T= {0,1},

生成式P如下:

S→0C,

B→0S,

S→1B,B→1BB,C→ 0CC。

B→0,C→1,

C→ 1S,

在此例子中,每个生成式的左部是单个非终结符,所以是2型文法。

3型文法或称正则法。生成式的形式为A→wB或A→w,A,

B∈N,w∈T*称右线性文法;如果生成式的形式为A→Bw或A→w,则称左线性文法。

以上介绍1型、2型和3型文法,对这三种类型文法的生成式形式都一些规定。如果对生成式的形式不加任何限制,则定义的文法便是0型文法.

以上定义的1、2、3型文法都是在0型文法的前提下所加的限制,所以必然都属于0型法。同理,3型文法也属2型文法,2型文法属1型文法。但要指出,在1型文法中不允许形式为A→ε的生成式存在,所以具有A→ε成式的2型或3型文法不能属1型文法。

由于文法有四类,所以由这些文法所产生的语言也有四类,即:由上下有关文法产生的语言称为上下文有关语言;由上下无关文法产生的语言称为上下文无关语言;由正则文法产生的语言称为正则语言;由0型文法产生的语言则称为无限制性语言。

但是我们日常使用的专门为2型语言文法,我们下一篇将要专门一篇文章讲解二型文法.