Video在线视频

欢迎同学们来到《软件理论基础》的MOOC课堂

我是清华大学的教师 罗贵明

今天给大家讲述的是第五章

正则文法和正则语言

内容包括有文法 线性文法

正则文法和正则语言

最后我们介绍自动机的积

首先我们介绍文法

文法最早的概念是由语言学家

在研究自然语言当中所完成的

语言是我们这门课里面关注的一个重点

我们知道语言实际上

是从自然语言里面得到的

语言它是取一个沟通作用

像人与人之间交流

它需要一种工具或者一个桥梁

像我讲话同学们能理解

同学们的讲话我能理解

这就是靠语言来作为一个沟通的渠道

那作为计算机 它也需要一种沟通渠道

在计算机研究的专家们

他们在研究计算机的这种表达形式

或者计算机的一种沟通的时候

他们怎么去创造一个计算机的语言

也就是说云跟计算机有一种沟通的渠道

计算机与计算机它有一个沟通渠道

而计算机跟人也有一个沟通渠道

这些彼此之间都需要理解

那怎么样去定义这种计算机的语言呢

人类的自然语言里面他有哪些规则

人类的语言他实际上跟文法相关的

文法实际上是语言当中的一种约束条件

下面我们看这几个句子

第一个句子 形式语言是字符串的集合

第二个句子 学生查阅资料

第三句子是 软件的测试是必要的

第四个句子 科学推动社会的发展

这四个句子虽然它表示的意义不一样

但从它们的形式上面

实际上我们可以把这四个句子

它们做这样的一种描述

第一个句子

它们可以表示成为形式语言

我们打一个方括号是字符串的集合

再打一个方括号

之后这个句号打一个方括号

第二个句子

实际上我们也可以

分成这三个方括号这种连接

第三个也是这三个方括号这种连接

第四个也是这三个方括号连接

那这三个方括号实际上

是这四个句子当中的

一个共同的一个性质

我们把这种句子的主体表示成为

这样的名词短语 动词短语跟句号

我们刚才给的是句子

一定是按这种次序排序

也就是说句号是在

名词短语 动词短语这之后的

你不能把它放在中间或者放在前面

那就不构成刚才的这种句子

刚才的名词短语会包括为

有形式语言 学生 软件的测试 科学

字符串的集合 资料 社会的发展

也就是说我们刚才的四个句子里面

名词短语包括有这些

那动词短语就包含有是字符串的集合

查阅资料是必要的

推动社会的发展

那这个句号

我们刚才给的句号就是几个符号 一个串

刚才的动词短语

还可以继续划分

动词短语可以写成为动词和形容词短语

或者动词和名词短语

那动词还可以划分为是 查阅 推动

这个形容词短语

在我们刚才的四个句子里面你看

必要的这就是形式短语

名词短语我们刚才已经讲了

在刚才的四个句子里面

有这一些是名词短语

我们把刚才的这个次序

名词短语 动词短语 句号在排序的

可以起一个名字叫句子

那这个句子实际上

也可以用一个树型的结构

来把它排序出来

这个句子在最上层

它可以产生出名词短语 动词短语 句子

这么一个次序

那名词短语呢

它可以产生学生

到了学生这里

大家看这个里面前面是带方块的

学生是不带方块的

这里再不会产生了

同样动词短语可以产生动词或名词短语

那动词可以产生查阅

名词短语可以产生资料

句号可以产生这么一个串

这个树型结构

句子就是

这个表示的是我们的树的根结点

学生查阅资料这个串

是我们这个树的一个叶结点

我们把叶结点从左到右排序出来

就是我们通过这个文法产生了一个句子

完整的句子

学生查阅资料句号

这就是我们从刚才的文法里面

推导出一个句子

那这个文法实际上可以抽象为

一个α到β的这个箭头产生的一个过程

这个句子看作是α的一个符号

后面β这名词短语可以看作一个符号

动词短语可以看作一个符号

句号可以看作一个符号

所以这句子它产生出后面这个串

那名词短语和动词短语呢

它还可以产生

你比如动词短语可以产生动词形式短语

动词短语还可以产生动词名词短语

名词短语你看可以产生学生

学生这个就不是带方括号的

我们等会儿对这种符号

我们进行一个定义

动词刚才在那个树形图里面我们产生查阅

名词短语我们产生了一个资料

句号产生一个串

就在我们刚才给的那个树型结构

实际上我们用这样的一套符号

把它完整的表示出来了

实际上在英文里面

它也有类似的一个表示

你看我们在英文的文法里面

我们表示实际上有这个句子Sentence

它可以产生名词词组或谓词

它是按这样一种方式产生的

这跟我们实际上很类似的

而名词词组呢

可以产生冠词和名词

谓词它可以产生动词

一个冠词

冠词它可以产生

冠词还可以产生z

这里实际上这边是带尖括号的

那这边是不带尖括号的

那我们再看下面名词

名词可以产生cat猫

名词还可以产生dog狗

动词这里面可以产生runs跑

动词也可以产生walks走

那通过刚才英文这类文法

实际上我们可以产生出the dog walks

这一句话通过我们刚才的文法

是怎么产生的呢

大家看这是一个sentence

它根据刚才的产生式

我们把产生式 把它代进去

实际上它可以产生名词词组 谓词

谓词它可以产生动词

所以我们把这个谓词

刚才的那个产生的符号

替换为一个动词

我们用双箭头这个推导来表示

名词词组它可以产生这个冠词和名词

你看 把这个产生式带进去的话

它又得到一个推导

这个冠词可以产生d

这个我们得到一个新的推导

因此 可以产生dog

这个又得到一个新的推导

动词产生了一个walks

它从刚才给的那一套文法

我们得到这样的一个句子

the dog walks

那刚才的文法不但是能够产生这个句子

还可以产生出下面这个句子

a cat runs

那这个产生的过程跟刚才的产生

实际上是类似的

按刚才的文法

还可以产生出下面这么多一些句子

这些句子都是按刚才的文法产生出来的

在文法里面

我们刚才给出来的这类产生

这里带尖括号像名词产生cat

名词产生dog

尖括号我们给它一个名字

把它叫做文法的变量

这个没有带尖括号的

我们也给了一个名字叫终结符

在这个产生式里面变量一定是在左边的

当然右边可以是变量

也可以是终结符

这就是我们文法里面

给的一个产生规则或者产生式

这在我们刚才讲的

汉语的表示 英文的表示

都遵从这样

那在我们刚才讲的

英文的语言的推导 汉语语言的推导

它的文法的推导

实际上都按了一定的推导规则

你像我们给了这类文学

S产生aSb

S产生ε

在我们的产生式里面

变量 一般是用大写的字母ABC

或者是其它的英文字母表示

而终结符 我们可以用小写字母

你像abc等等

这跟我们之前讲语言的时候

我们的规定是一样的

这个ε是空串

那我们把刚才的文法

实际上可以抽象为这样的符号了

这就是两个产生式

两个产生式 我们根据这个产生式

你看怎么去定义推导呢

我们S

S里面是我们刚才这个文法里面的变量

这个推导它用了这边的一个产生式

产生式得到了推导

产生式是文法里面给到的

推导是用了这给定了文法

那下面我们在这一个串里面

这里面有终结符 有变量

我们把这个变量

假如用第二个产生式S还是ε

把ε去替换S就得到这类关系式

这就得到另外一个推导

所以这样的一个文法

它就推导出ab这个句子出来了

这是从文法推导的关系

那我们还有从这个文法

可以推导出另外一个句子

像S 我用第一个产生式得到了aSb

再用第一个产生式 它可以得到aaSbb

用第二个产生式我们就得到aabb

所以这类文法

我们还可以推出这个句子aabb

当然我们还可以得到

通过这个文法 还可以得到

更多的一个推倒

像这里面从文法可以推导出aaabbb

还可以推导出aaaabbbb等等

实际上它还可以推导出这样的一个串出来

a的n次方 b的n次方

n大于或等于0

这个语言在我们的文法里面

很简单能够推导出来

但是在我们前面讲的自动机里面

我们说它用NFA或者DFA是构造不出来的

这是通过文法我们可以推导出句子

我们把这些推导的串放在一块

构成了一个语言

这文法它实际上

也可以推导出一个语言出来

我们下面要给文法的一个定义

文法的定义在我们前面讲到文法的

一些概念的时候

那它最重要的或最基本的要素有哪些呢

你像我们用到文法的变量

也就是用尖括号表示的类似于变量

再用到了终结符

终结符就是没有尖括号的

还有我们用到了文法从哪个地方开始的

所以开始变量很重要

在文法里面最重要的是产生式P

所以我们文法实际上是一个四元组

这个四元组 V是变量的集合

P是终结符的集合

S是开始变量

P是产生式的集合

在这个里面

我们的变量或终结符是两个不交的集合

你看它们交一定等于空

而开始变量一定是变量当中的一个符号

在文法里面最重要的

我们刚才强调 实际上就是产生式

在我们这里给的产生式 大家就可以看出

产生式的左边一定是一个变量

也就是a乘上α

a是V中的一个变量

而它的右边呢

在我们刚才讲的文法里面

大家可以看出它可以是变量

可以是终结符

它可以是变量和终结符混合成的一个串

所以我们表示成为V和T的闭包

这是我们在第一章里面

给出的一个定义形式

这就是我们给的文法它的一个定义

形式化定义

根据这个定义

我们看刚才给的这种文法

这个文法里边呢

它表示成四元组

V,T,S,P的话

V只有一个变量S

而终结符这里面a和b

是终结符 是两个符号

那开始变量这里

它只有一个变量 开始变量 也就是S

产生式 这里面

在文法里面 这产生式 这里有两个产生式

在文法里面我们一般来说

是表示成四元组

当我们书写的时候

我们有时候你把产生式

把它表示出来了

那大家就可以对这个文法呢

已经很清楚了

因为在这个产生式里面

它的变量和终结符

我们规定了

哪些符号是变量 哪些符号是终结符

自己清楚了

在这个里面开始变量

开始变量我们默认是在已给的

这些产生式里面

第一个产生式最左边的一个变量

我们表示成文法的一个开始变量

或者是又定为文法的开始变量

那文法的这个四元组实际上

你给了这个产生式 我们就知道

这个文法它是怎么表示的

用刚才的文法

推导出的字符串

有的是完全是变量构成串

有的是终结符构成串

那我们给一个定义呢

如果是有变量和终结符构成串的话

混合在一块

我们把这样的字符串叫做句型

那如果是你这给了字符串

完全是由终结符构成的话

我们把这样的字符串叫做句子

像这个文法

我们就可以得出像这样的字符串

它既有终结符又有变量

这样的字符串既有终结符又有变量

这样的字符串有终结符还有变量

所以这个叫做句型

而这个字符串它只有终结符

所以它就是句子

那我们的文法里边

当然最后是讨论语言的

语言实际上它是由句子来构成的

我们在文法里边这个推导是非常重要的

那如果是我们只强调最后推导的结果

不强调中间的推导过程

你比如说我这个给了这个文法

从开始变量它可以推导出它

也可以推导出它

也可以推导出它

也可以推导出它

通过这一个文法

从这个变量S 可以推导出aabb

我如果省略了中间这些步骤的话

我只关心结果

这就是我们得到文法的

它到推导闭包

我们可以把它表示成为这个S

这个推导上面的一个信号

aaabbb

这个就是说这个变量S

在这个文法里面

它经过若干次的推导可以得到aaabbb

这一定是在这个文法里面

所以有时候我们强调

是在这个文法里面

我们就把这个文法

把它标一个是哪个文法标里面

如果我们知道这个文法的话

我们有时候就把这个文法

这个记号就去掉

这是我们在推导的时候

用的推导闭包

当然这是一个描述性

我们可以用形式化来定义 对一般情况

如果有这类字符串w

它在文法里面可以推出w1

可以推出w2

w2可以推出w3

都是在文法里面 再以及推出Wn

也就是说w1这个串经过文法

可以推出Wn的话

我们一般就可以这样写w1

在这个文法里面经过若干次的推导

最后推导出Wn

这种定义 实际上我们可以用归纳的定义

也就是我们首先约定

任何一个串经过0次推导

可以推导出它自己

就是w在*下推导出w

然后再根据归纳假设 再进行归纳推导

这样我们就得到通过归纳的形式

来定义它的闭包

这个推导闭包

实际上在我们文法里面非常重要

特别是在后面的语言的定义里面

我们给了这个文法G

假如是S产生aSb、S产生ε

这些是刚才给的例子

它通过这个产生式S可以推导出ε

S可以推导出ab

S可以推导出aabb

S还可以推导出aaabbb

你看这个推导我们只强调了

最后的推导结果

中间的过程我们就省略了 不太关心

实际上它中间每一步都是通过这个文法

来推导出来的

这样我们这个表示

实际上就得到从这个变量

它可以推导出哪些结果出来

那它这推导还可以推导出

这样的一些结果

我们给出了文法它的产生式

到推导它的表示

而且怎么样通过推导闭包

把推导最后的结果写出来

在文法里面那我们还可以给出一些

另外更简洁的一些记号

因为我们在文法里面

它最左边是一个变量

如果在这些产生式里面

最左边变量都相同的时候

我们可以把它表示成为这样的一种形式 你像

A产生小a大Ab这个产生式

再把另外一个产生式

我们用一个虚线把它分开

A产生ε把它写到这里

像这种记号 在大家编程当中也用了很多

我们下面α产生β、α产生γ

就可以表示成为α产生β

或者α产生γ

那下面我们再看另外一个例子

给了这个文法

S产生大Ab

S产生a大Ab

你看我们再用到另外的一个产生式

a产生ε

这实际上就给出了三个产生式

那这个文法它的推导

可以推导哪些呢

通过第一个产生式S产生大Ab

通过a产生ε

我们可以推导出这个推导出b

这是用的这个文法的

第一个产生式或第三个产生式

那我们还可以通过s可以推导出abb

还可以通过这个文法这个s推导出aabbb

这个文法我们可以在这个文法的推导下

推导出更一般的aaabbb

我们如果不考虑中间的这些推导

我们最后显示的

你看它实际上这个规律

我们可以看出

它这个句子产生的规律

我们把句子产生规律

可以把它最后得到是a的n次方

b的n次方b

得到这样一个句子

这个句子我实际上

就是一般的这个文法推导的形式

我们可以通过这个句子

可以把这个文法的它的语言

实际上可以表示出来

所以给了这个文法

它的语言

我们有了推导闭包之后

我们可以给出语言的一个定义

这个语言就是在这个文法里面

它从开始变量

这文法里面经过若干次的推导

最后推导出的终结符的串

我就把这个终结符的串

放在这个集合里面

这个集合就叫做这个文法G的语言

这样给出的语言 它的定义

计算机它是能理解的

这实际上就是语言的一个形式化定义

下面我们看这个例子

S产生大Ab

a产生小a大Ab

再或者是aa产生ε

这就是我们刚才讲过的例子

它的推导

我们刚才讲了

S可以推导出a的n次方 b的n次方 b

这就是在一般的文法里面推导

它可以有这种推导形式

也就是说这个句子从开始变量

它可以推导出来

我们把它一般这个推导实际上

可以把它的语言就可以表示出来

这个语言就是a的n次方 b的n次方 b

这样用我们的推导闭包

很容易表示这类语言

那上面我们给出了

这个文法的它的描述

文法的定义和文法的推导

在下一节里面

我们还要讨论一些特殊的文法

好 这一节的内容我们讲到此

谢谢大家