Video在线视频

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

现在介绍第四章 正则表示的第三节

就是正则表示和语言

首先看这么一个例子

这是一个NFA自动机

它描述的语言大家可以看出

实际上这里从q0初始状态到q1

它到终态的话 这个路径

经过0回到q0

因此1，0被接受

空串当然被接受

再然后多次1，0、1，0

都是被接受的

因此它的语言可以表示成为这种形式

这种形式根据我们之前介绍的*闭包

实际上这个语言就可以写成10的*闭包

你看这是自动机

它的语言是集合

它也可以写成这种形式

对计算机而言

这个集合表示是肯定很复杂的

但是这种表示很简单

那下面我们对这种表示专门做一个介绍

这就是我们介绍的正则表示

正则表示从刚才的介绍我们看

它是可以表示语言的

就像这个正则表示

它可以表示成这样的语言

那这种正则表示

怎么样可以展示出这种语言呢

这就是下面我们给出

这样的正则表示它的定义

正则表示的定义

我们是从文法上面来给的定义

我们是用归纳的方法来给定义

首先这三种符号 空集 空串 单个的输入字母

我们说它是正则表示

这个就更简单

这是我们的基础

我们原来讲归纳法 归纳法

总是在证明的时候用的归纳

现在我们就要用定义也用归纳

这就是我们的归纳基础

归纳假设

假设r1、r2 它们都是正则表示

给了两个正则表示

那接下来我们就说r1+r2

它是正则表示

r1.或者*r2

r1*闭包

（r1）都是正则表示

至于这个加这个点

或者乘这个* 这个括号是什么意思

我们在文法里面不关心它

我们只关心这种表示

它是合理或者是正确就可以了

也就是说我们判定一个表示

是不是正则表示

是不是符合这个定义

下面我们看

这个就是 我们给的一个正则表示

因为我们说单个字母是正则表示

这个正则表示 有正则表示中间加一点

当然我们也可以把这个点也可以省掉

这个没关系

你叫乘也可以，叫连接也可以

这个是正则表示

两个正则表示加起来

做一个加是正则表示

正则表示括号也是正则表示

正则表示之后再做一个*记号

*闭包也是正则表示

所以前面这个表示就是一个正则表示了

那看后面单个字母是正则表示

空集是正则表示

两个正则表示的这个加，得到的是正则表示

然后这个正则表示括号是正则表示

所以前面一部分是正则表示

后面一部分是正则表示

两个正则表示再加一点也是连接

得到的就是正则表示了

这个那我们定义这个是正则表示

它是正确的是合法的

那看哪个不是正则表示呢

像这里给的一个表示

a是正则表示，b是正则表示

两个做一个加是正则表示

那后面这个加在没有符号的时候

那在我们定义里面就没有这种形式了

所以这种表示或者这种符号

就不是正则表示了

在正则表示里面

它有运算像我们加有一个点 也叫连接

还有一个*运算

那有这些运算

我们就应该给这些运算 给它们的优先级

那优先级

我们是这样规定的

*运算也叫闭包运算 级是最高的

其次就是连接运算

这个是它的优先级比*运算要低一些

之后是加运算 也叫并运算

这个运算的优先级是最低的

下面我们再看正则表示的它的语言

因为我们前面讲了正则表示

它是可以表示语言的

假设给了一个正则表示

它的语言我们用就L（r）表示

至于这个L（r）怎么定义

那下面我们会按它的形式

给出它逐步的展开

像这样给出的一个正则表示

它的语言应该是这样一个集合形式

至于这个集合是怎么得到的

我们下面就给出正则表示

它的语言的一个定义

因为我们的正则表示是递归定义

所以我们对正则表示的语言

也是按它的递归进行一个说明

首先对基本的正则表示

也就是我们的归纳定义的基础

空集

空集的语言，我们就定为空集

空串

空串的语言我们定义

包含空串的集合

单个字母它的正则表示的语言

就是包含这个字母的一个集合

这样我们给出了正则表示

它的基础的空集 空串

或单个字母它的语言定义

那对一般的正则表示

我们怎么给它定义呢

下面我们就是用归纳定义

假设r1是正则表示

r2是正则表示

它们对应的语言分别为L（r1）或L（r2）

那我们下面就讨论r1+r2这个正则表示

它的语言实际上是L（r1）或L（r2）

这两个语言的并

从这个语言里面我们就知道

正则表示这一个+

实际上在语言里面它表示一个并的意义

再看r1、r2两个正则表示

它们连接或者做了一个点

得到这个正则表示

它对应的语言是

r1这个语言与r2这个语言

两个语言做连接的

那从这里我们也可以看出

我原来在正则表示这个点

实际上在语言里面是它们的连接

正则表示（r1）

它的语言实际上跟r1的语言是一样的

也就是说你加了括号得到的正则表示

实际上跟原来的它表示的形式是一样的

r1正则表示 作为*闭包

作为*闭包 它得到的语言

就是r1这个语言作为*闭包

也就是我们第一章介绍的kleene闭包

那到现在我们对正则表示 它的语意

全部都解释完了

我们就知道前面表示的正则表示

这个符号 这个符号

这个符号和这个符号

它在语言里面代表的意义

都定义的非常清晰了

下面我们看

通过定义它这么一个正则表示

它的语言

怎么来通过定义把它求出来

这个正则表示是由这一个正则表示

和a*这个正则表示

两个正则表示它们的连接

作为语言根据我们正则表示语言的定义

它就是分别为这个正则表示的语言

与这个正则表示的语言做连接

那在对这样的正则表示

带括号的和不带括号的正则表示

它们的语言是一样的

对这个正则表示

我们根据定义

可以把它写成为这个正则表示

它的语言的*闭包

而前面这两个正则表示

它做加之后的语言

就分别为这个正则表示的语言

与这个正则表示的语言 它们做并

这样我们就把它分解为

到了这个语言的表示了

到这一部分

我们就可以把它的语言就得到了

你像单个字母a

它对应的语言就是包含a这个集合

单个字母b 表示的正则表示对应的语言

就是单个字母b这个集合

这也是a它做*闭包

那到这里我们直接按集合的运算了

就是ab这个集合

这个按我们的kleene闭包或者*闭包

得到这个集合

然后把它们做连接之后

就得到这个语言的集合

也就是说在给了这个正则表示

或它的语言

通过我们的定义 就得到这种形式

这也是我们之前给出的这个正则表示

它的语言的形式

就是按这样的定义得到的

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

这里给了a+b *闭包

在与后面的a+bb再连接

它的语言我们同样可以按

前面的那个定义形式

把它的语言给出来

这个语言我们就直接

可以得到这样的形式

我们再看一个例子

这个正则表示是aa 它们做kleene闭包

bb做kleene闭包

最后连接的b

这一看这书写形式 依然是我们的正则表示

只是我们把中间的这个连接的点

可以加上 也可以省掉

那它对应的语言

实际上我们

根据这里的表示 很容易写出来

这个写的 我们直接写的是

它正则表示的语言是a的rn次方

b的rm次方再连接b

n和m是大于或等于0的整数

这样我们可以把正则表示它的语言

实际上跟前面

按这种形式 都可以展示出来

下面我们再看这一个正则表示

这个正则表示 前面是0+1*闭包 00

后面是0+1*闭包

这个语言我们直接按前面的方法

把它展开求得

但是我们看实际上这个语言

还可以用自然语言把它表示出来

那它的自然语言是什么呢

实际上大家看 它这里面

得到的语言的串里面

必须有两个连续的0

所以这个正则表示

它表示的语言实际上是

里面都含有两个连续的0的字符串

对于这样的正则表示

这前面是（1+01）*闭包 连接一个0+ε

那它的语言

我们说这个语言

也可以用自然语言表示出来

这个语言实际上是我们刚才表示的

正则表示的语言它的补

实际上就是没有两个连续的0的字符串

那对于正则表示，它可以表示语言

那我们给了多个正则表示的时候

它们实际上有的可能它们的语言相同

如果对于给了正则表示r1、r2

它们的语言是相同的时候

也就是说对应的语言是相等的

我们把这样的正则表示称为是等价的

并且记为r1=r2

实际上这样定义一个等价

我们可以去验证等价关系

也就是说这个正则表示

和这个正则表示写成这个等于

这个等于是一个等价的

一个意向的一个等于

下面我们看

再给出语言 我们刚才已经讲过了

所有没有两个连续0的字符串

实际上开始给了这样的正则表示

实际上还可以给出另外的

这种正则表示

它也表示的语言是这样的

这两个正则表示

表示的语言都相同

因此它们这两个语言都是L

那它们这两个正则表示实际上是等价的

也就是r1、r2是等价的正则表示

这跟我们之前讲的自动机DFA、NFA

实际上有一些相关

我们讲了对于一个语言

正则语言

它可以有多个NFA或者DFA

只要是它们表示的语言相同的话

我们定义这个自动机是等价的

对于正则表示也是的

只要是它们表示的语言是相同的话

那正则表示 它就是等价的

当然这里面呢

有了正则表示

它表示的语言是相同的 但是它简单些

有的正则表示它要复杂些

这里面就有一些

怎么将一些正则表示从复杂的

画到一些简单的一些步骤

这是我们后面要讲的

正则表示的一些代数率

下面我们再看这类语言

由0、1交替构成的字符串

那这个语言它的正则表示

可以写成这种形式

当然还可以写成这种形式

还可以表示成为这种形式

这些都可以表示这个语言

所以这些正则表示都是等价的

刚才我们介绍了正则表示

它的定义或正则表示它的语义

正则表示它可以表示语言

那这个语言我们从刚才的

它的结构语言的表示形式看

它实际上都是正则语言

那是不是所有正则表示

它表示的语言都是正则的呢

这就是我们下一节要介绍的

正则表示与正则语言的关系

好，这一节就到此

谢谢大家