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

第一篇:集合与推理方法

1:我们为什么要学习形式语言与自动机

任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们很流行的框架和工具很有可能几年内就会变成过时的东西.但是计算机科学的整体的思维不会变,在学习中,我们更要应该看思考能力的培养,如何清楚的表达自己的能力,如何清晰地解决问题的能力以及自己还欠缺的能力.这方面的东西在我看来,是具有持久的价值的,学习理论能够拓展人们的思维,并能使人们在这方面得到训练.

说回形式语言与自动机,大家在大学学习中可能离形式语言与自动机的一门课应该是<编译原理>,<编译原理>中是会讲到形式语言和自动机的部分东西,另外有的学校可能就有专门的这一门课,比如北航和哈工大等等.说到底,形式语言与自动机其实是一门将数学系统应用于计算的一种模型.所以我想用这一系列文章来重点介绍形式语言以及与之相对应的自动机体系.

形式语言给出了语言的语法规则和分类的形式化方法,而自动机则描述了能够识别的语言的自动装置.这样的形式化的描述以及自动机的工作原理将会是这一系列文章的核心.这一些核心在编译理论,人工智能,现代安全学和通信中都有着极强的应用,是每个对于计算机科学感兴趣的人都应该熟悉的内容.

这一系列文章我现在想先简单的分为三大部分:

第一部分是基础的预备知识的学习

第二部分是讲述四类文法所产生的语言以及这些语言的识别装置

第三部分是讲述这四类文法的理论在实际生产中的应用

但是上述的理论可能会比较枯燥,所以我也想大家有兴趣可以配合蒋宗礼老师的<形式语言与自动机理论>,加上上边的习题,效果会更好,更加的容易理解和接受.

2:什么是形式语言与自动机?

形式语言和自动机的理论是计算机科学的理论基础。这些理论来源于 :

(1) Chomsky对自然语言的研究; (2) 巴科斯和诺尔使用巴科斯-诺尔范式(BNF)对 ALGOL 60 语言的语法规则进行描述; (3) Kleene在研究神经细胞时建立的自动机模型。 形式语言理论的研究对象与以前所有语言的研究对象不同 , 不止是自然语言 , 而是人类的

一切语言 : 既有自然语言 , 也有人工语言 , 包括高级程序设计语言。 形式语言和自动机的理论已经成为计算机科学 的理论 基础 , 其 应用范 围已 被扩展 到生 物

工程、自动控制系统、图像处理与模式识别等许多领域。

3:学习之前所需要的知识

在学习形式语言之前,我们首先要明确下所需的集合,图论,逻辑证明这样的知识,这些知识难度不会超过高等数学的难度,如果你已经会了,就直接跳过去吧,如果不会就可以继续看下去.

1:集合

当我们去研究一类对象的时候,我们可以将具有同一类对象的整体看作是一个集合,组成一个集合的对象称为该集合的元素

如果设A是一个集合,a是集合A的一个元素,就可以表示为a∈A,如果a不是集合A的元素,就可以表示a∈|A,也就是a不属于A

以后我为了省事,比如a属于A,b属于A,c属于A的,都写成a,b,c∈A.

有限个元素x1,x2,.......,xn组成的集合,称为有限集合.无限个元素组成的集合,称为无限集合.比如,整数构成的集合是一个无限集合.

不含元素的集合,称为空集,符号是:∅

2:集合之间的关系

(1) 设两个集合A、B包含的元素完全相同,则称集合A和B

相等,表示为A=B。

例如,集合A={a,b,c},集合B={b,a,c},则有A=B。 这里强调, 一个集合中元素排列的顺序是无关紧要的。 有限集合A中不同元素的个数称为集合的基数, 表示为 #A或A。

例如,B={a,b,c,4,8},其基数#B=5。

(2)设两个集合A、B,当A的元素都是B的元素,则称A包

含于B,或称A是B的子集,表示为A∈B。当A∈B且A≠B, 称A是B的真子集,表示为A B。

如果所研究的集合皆为某个集合的子集时 , 称该集合为全集 , 记为E

(3) 根据(1)和(2) ,对于任意两个集合A、B,A=B的充要条 件是A∈B且B∈A。

3:幂集

设A是集合,A的所有子集组成的集合称为A的幂集,表示 为2A或ρ(A)。

例 如 ,A= {a,b,c} ,

则 有ρ(A) = { ∅,{a},{b},{c},{a,b},{b,c}, {a,c},{a,b,c}}

当A是 有 限 集 , #A=n, 则 ρ(A) 的 元 素 数 为C0n+C1n+…+Cn=2n

但是有一个例外,空集∅是任何集合的一个子集

4:集合的运算

( 1 ) 设 两 个 集 合A、B, 由A和B的 所 有 共 同 元 素 构 成 的 集 合,称为A和B的交集,表示为A∩B。

(2) 设两个集合A、B, 所有属于A或属于B的元素组成的集 合,称为A和B的并集,表示为A∪B。

(3) 设两个集合A、B, 所有属于A而不属于B的一切元素组 成的集合,称为B对A的补集,表示为A-B。

(4) 设两个集合A、B,所有序偶(a,b)组成的集合,称为A、B的笛卡尔乘积,表示为A×B。

A×B={(a,b)|a∈A且b∈B}

比如:A = {a,b,c},B={0,1},则A*B = {(a,0),(a,1),(b,0), (b,1), (c,0) ,(c,1) }

但是要注意一点,序偶的元素排序是有顺序的,不能够随意的颠倒,(a,b)和(b,a)是不同的两个序偶,所以说如果两个序偶相等, 应该是对应元素相同, 例如,(a,b)=(c,d),应有a=c和b=d。

对任意集合A、B、C有如下运算律:

(1)A∪A=A,A∩A=A; (2)A∪B=B∪A,A∩B=B∩A;

(3) (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C);

(4)A∪(B∩C)=(A∪B)∩(A∪C),A∩(B∪C)= (A∩B)∪(A∩C); (5)A∪(A∩B)=A,A∩(A∪B)=A; (6)A∪A=E,A∩A= ∅ (7)A∪B=A∩B,A∩B=A∪B; (8)E∪A=E,E∩A=A;

(9)A∪∅ =A,A∩∅ =∅

5:关系

说到关系,我们平时用的大于,小于,等于,包括等都是属于关系,下面我引用蒋老师的书中的描述来说一下关系的形式定义:

定义1.1.1 设A是一个集合,A×A的一个子集R,称为是 集合A上的一个二元关系,简称关系。

对于a∈A,b∈A,如果(a,b)∈R,称a和b存在关系R,表示 为aRb;如果(a,b)∈|R,称a和b不存在关系R,表示为a/Rb。

例如 , 自然数集合N中的大于关系 , 可表示为 > ={(a,b)|a,b∈N且a>b}

当有两个集合A、B,则从A到B的关系是A×B的一个子集。

定义1.1.2 设集合A,R是A上的关系:

对每个a∈A,如果有aRa,称R是自反的; 对 于a,b∈A, 如 果 有a R b, 又 有b R a, 称R是 对 称 的 ; 对 于a,b∈A, 如 果 有a R b和b R a, 则 必 有a=b, 称R是 反对称的 ; 对于a,b,c∈A,如果有aRb和bRc,则有aRc,称R是传递的;对每个a∈A,如果a/Ra,称R是反自反的。

例如 , 数之间的相等关系 , 具有自反性、对称性和传递性 , 小于 关系和大于关系没有自反性 , 但有传递性。

定义1.1.3 设R是非空集合A上的一个关系,如果R有自 反性、对称性和传递性 , 则称R是一个等价关系。

由等价关系R可以把A分为若干子集, 每个子集称为一个等 价类 , 同一等价类中的元素互相是等价的.

定义1 .1 .4 设R是集合A上的一个关系,如果R有自反性、 反对称性和传递性,则称R是偏序关系(或部分序关系)。

这个值得说一下,现在套用书中的例子

设集合C={2,3,6,8},R是集合C上的整除关系,即R= {(x,y) |x,y∈C且x整除y}

可以得到:

R= {(2,2), (3,3), (6,6), (8,8), (2,6), (2,8), (3,6)}

结合上面的偏序关系,我们可以描写出关于偏序的图,叫做哈斯图,有兴趣的可以百度了解下,并不是很重要的东西.

定 义 1 . 1 . 5 设R是 集 合A上 的 关 系 , 如 果 另 有 关 系R′满 足:

(1)R′是传递的(自反的,对称的) ; (2)R′R; (3) 对任何传递的(自反的、对称的)关系R′′,当有R′′R,就

有R′′R′,则称关系R′是R的传递(自反、对称)闭包。R的自反闭包表示为r(R),R的对称闭包表示为s(R),R的

传递闭包表示为t(R)。如果给定一个集合A上的关系R, 可用以下方法找出传递闭

包t(R),自反闭包r(R)和对称闭包s(R):

(1)r(R)=R∪IA,其中IA ={(x,x)|x∈A};

(2)s(R)=R∪R-1;

(3)t(R)=R∪R2∪…∪Rn,其#A=n。

举个例子:

设集合A={a,b,c},A上的关系R={(a,b),(b,b), (b,c)},则R的传递闭包为

t(R) = {(a,b) , (b,b) , (b,c) , (a,c)} , 而R的自反传递闭包表示为

tr(R) = {(a,a), (a,b) ,(b,b), (b,c), (a,c) ,(c,c)}。 今后用R+ 表示R的传递闭包,用R* 表示R的自反传递闭包。

定义1.1.6 映射是关系的一个特殊类型 , 也称函数。设集合A和B,f是从A到B的一个关系,如果

对每一个a∈A,有惟一的b∈B,使得(a,b)∈f,称关系f是函 数,记为f:A→B。

如果存在(a,b)∈f,则a是f的自变量,b是f作用下的像点,因此(a,b)∈f亦可写成f(a) =b。

由 定 义 1 .1 .6 可 知 , 函 数 有 如 下 特 点 :

(1) 函数f的定义域是A, 不能是A的某个真子集。

(2) 一个a∈A只能对应于惟一的一个b,或者说f(a)是单值的。

f的值域是B的子集,记为Rf。

函数的几种特殊类型是 :

(1) 对于f:A→B。如果f的值域Rf =B,即B的每一个元素

都是A中一个或多个元素的像点,则称f是满射的。 例如,集合A={a,b,c,d},B={x,y,z},如果f:A→B为:

f(a)=x,f(b)=x,f(c)=y,f(d)=z则f是满射的。

(2) 对于f:A→B。如果A中没有两个元素有相同的象点, 则称f是入射的,即对于任意a1,a2∈A:

如果a1 ≠a2,则有f(a1)≠f(a2),或者如果f(a1)=f(a2), 则有a1 =a2。

例如,集合A={a,b},B={x,y,z},如果f:A→B为:f(a) =x,f(b)=y,则称f是入射的。

(3) 对于f:A→B。如果f既是满射的,又是入射的,则称f是双射的 , 或称是一一对应的。

例如,集合A={a,b,c},B={1,2,3},

如果f:A→B为f(a) = 3,f(b) = 1,f(c) = 2

则称f是双射的,或者说是一一对应的。

定义1.1.7 设非空集合A,∏={π1,π2,…,πn},其中πi n

A,πi≠∅ (i=1,2,…,n),如果有∪πi=A且πi∩πj=∅ (i≠j),i=1

则称∏是A的划分。其中πi是一个划分块。

例如,集合S={a,b,c,d},考虑下列集合:

A={{a,b},{c,d}}

B= {{a},{b},{c},{d}}C= {{a},{b,c,d}}

D= {{a,b,c,d}}E={{a,b},{b,c,d}}F= {{a,b},{c}}

则A、B、C和D都是S的划分,E和F则不是S的划分。

定义1.1.8 设有集合A、B,如果存在双射函数f:A→B,则 说A和B有相同的基数,或者说A和B等势,记为A~B。

一个无限集 , 存在着它与其自身的一个真子集有 相 同的基数。这里Ne 和自然数集合都是无限集。

通常 , 考虑一个无限集的基数时 , 总是看它与自然数集合能否 建立一一对应。能与自然数集合建立一一对应的无限集称为可数集 ; 不能与自然数集合建立一一对应的无限集称为不可数集。

例如:整数集合是可数集; 集合{1, 3, 5, 7, …}是可数集; 实数 集合R是不可数集;集合{x|x∈R,0<x<1}是不可数集,其中R是实数。

6:证明和证明方法

形式语言和有限自动机,有很强的理论性, 许多的论断是以定理的形式给出的,而定理的 正确性是需要进行证明的。

形式语言和有限自动机理论中定理的证明大多使用反证法和归纳法进行。

(1):反证法

反证法也称为归谬法。利用反证法证明一个命题时 , 一般的步骤为 :

假设该命题不成立; 进行一系列的推理; 如果在推理的过程中,出现了下列情况之一:

1 与已知条件矛盾;

2 与公理矛盾;

3 与已证过的定理矛盾;

4 与临时的假定矛盾;

5 自相矛盾。 由于上述矛盾的出现,可以断言“假设该命题不成立”的假定是不正确的; 肯定原来的命题是正确的。

(2)归纳法

归纳法就是从特殊到一般的推理方法。分为完全归纳法和不完全归纳法两种形式。

完全归纳法是根据一切情况的分析而作出的 推理。由 于必 须考虑 所有 的情况 , 所 以得 出 的结论是完全可靠的。

不完全归纳法是根据一部分情况作出的推理 , 因此 , 不能作为严格的证明方法。 在形式语言与有限自动机理论中 , 大量使用数学归纳法证明某个命题。数 学 归 纳 法 可 以 使 用“ 有 限 ”步 骤 来 解 决“ 无 限 ”的 问 题 。数学归纳法的原理为 :

假定对于一切非负整数n, 有一个命题M(n) , 假设证明了 :

(1)M(0) 为真; (2) 设对于任意的k≥0,M(k) 为真,如果能够推出M(k+ 1) 为真,则对一切n≥0,

M(n) 为真。因此,在使用数学归纳法证明某个关于非负整数n的命题P(n) 时,只需要证明(1)、(2)

两点即可。第(1)步称为归纳基础, 第(2)步称为归纳步骤。第(2)步中“设对于任意的k≥ 0,M(k) 为 真 ”, 称 为 归 纳 假 设 。

在实际应用中,某些命题P(n)并非对n≥0都成立,而是对n≥N(N为大于0的某个自 然数)成立, 此时,也一样可以使用该归纳法。具体步骤如下。

假定对于一切非负整数n, 有一个命题M(n), 假设证明了:

(1)M(N) 为真; (2)设对于任意的k≥N,M(k)为真,如果能够推出M(k+1)为真,则对一切n≥N,

M(n) 为真。

比如说用归纳法证明下递归:

归纳法证明递归定义集合性质的步骤如下。(1) 基础:证明该集合中的最基本元素具有性质P; 而且使得该集合非空; (2) 归纳: 证明如果该集合的元素x1 ,x2 ,x3 , …,具有性质P, 则使用某种运算、函数或组

合方法对这些元素进行处理后所得的元素也具有性质P;

(3) 由归纳法原理,集合中的所有元素也具有性质P。

这上述的大概是集合的能够概括的所有知识点了,只需要了解即可,在下一篇文章中,将会描述一下逻辑和图论的问题,然后基础知识将很快学完,开始真正有意思的部分