Video在线视频

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

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

正则语言的运算性质

之前我们介绍了正则语言

怎么判断一个语言是正则呢

我们现在有两种方法

要么这个语言它的DFA你能够画得出来

那这个语言就是正则的

要么解释这个语言的NFA可以画出来

那这个语言也是正则的

除此之外，我们现在还没有其他的方法

能够判断一个语言是正则的

但有时候我们知道一些语言

它已经具有一些性质

根据这些性质进行一些运算之后

得到新的语言

那我们能不能通过

原来的语言的主要的性质

来判断这些新的语言的性质呢

这就是我们通过正则语言的运算

来判断语言的性质

你比如说我们给了正则语言a1、a2

它们的连接运算

它们的并运算

它们的新运算

还有它们的反转、它们的补

通过了这些运算之后

这些语言是不是还是正则的

如果这些语言

通过这些运算依然是正则的

我们就说这些正则语言

对于这些运算，它是封闭的

下面给了正则语言L1

任何一个正则语言

它应该对应一个NFA

而任何一个NFA

都等价于只有一个终态的NFA

所以我们假设L1它对应的

只有一个终态NFA 是M1

正则语言L2

同样它也对应一个只有一个终态的NFA，M2

那下面的讨论当中，我们都做这样的假设

我们给了这个L1是个正则语言

它对应的这里的自动机是M1

L2这个例子

它对应的NFA是只有一个终态的M2

我们下面在进行运算的时候

我们也把这两个例子

作为我们要介绍的实例

首先我们介绍第一个性质就是语言的并

正则语言的并

L1、L2都是正则语言

它们并了之后

我们看它们的自动机能不能构造出来

这是我们刚才讲的L1对应的自动机

NFA M1

这个是L2对应的NFAM2

通过这两个自动机

要构造一个新的NFA

那么我们只需要加一个初态

或加一个终态

再分别用ε把它连接起来

这得到的NFA也只有一个终态

但这个NFA 它接受的语言

从这个构造的原理我们可以看出

它要么到这个自动机里面再接受

要么到这个自动机里面接受

来得到的就分别是语言L1或L2的并

我们从这里看L1并L2

它的NFA我们能不能得到

所以L1并L2就是一个正则语言

我们看这个例子

另外一个是L2的一个例子

那它得到的并自动机就是这样的

它的语言也就是这两个语言的并

下面我们介绍正则语言的另外一个运算

就是语言的连接

假设L1、L2都是正则语言

那它们的连接是不是正则语言呢

假设L1对应的只有一个终态的NFAM1

L2对应的只有一个终态的NFA M2

那这两个自动机我们要做连接的话

构造新的NFA

就我们增加一个终态

这前面 把前面的M1的初态

作为新的自动机的初态

这里增加一个ε转移

再增加一个终态的ε转移

这样得到一个新的

只有一个终态的NFA

它接受的语言很容易验证

就是L1、L2两个正则语言的连接的NFA

两个正则语言的连接

依然是正则语言

我们看这个例子

它两个自动机的连接

就是我们这两个正则语言的

得到的新的语言

这就是a的n次方bba

那下面我们再看正则语言的

新的一个运算

叫星运算，星闭包

假设a1是正则语言

它们做星运算是不是还是正则语言

也就是说它的NFA我们构造出来

L1对应的自动机是M1，只有一个终态

要构造它的星闭包的自动机

也就是它接受的语言做任意一次的连接

依然在这个语言里面

那我们只需要

增加一个初态，增加一个终态

然后增加一个ε迁移

这样这个语言它做任意一次它的连接

都在这个语言里面

但是我们要注意

在这个语言里面 星闭包它包含有空串

那么如果是原来的这个自动机里面

它有空串

那么ε是L1*的

但我们并不一定知道

原来的语言里面包含ε

所以在这种情况下

我们必须要增加一个ε转移

这个转移就保证了

这个自动机一定包含空串ε

我们下面看这个实例

这个就是对应a的n次方b的

它的自动机M1

它增做了增加了这里ε迁移和这个状态之后

得到的是L1的星闭包

这样正则语言的形式上依然是正则语言

下面我们再看正则语言的反转

我们给了正则语言L1

它对应的自动机M1

它的反转的自动机能不能构造出来呢

在这里我们只需要

把它所有的迁移都反转

而且它的初态和终态也进行一个互换

因为我们讲了L1只有一个终态

所以这里的互换是可行的

那这样得到的自动机M′

它对应的语言就是L1这个语言的反转

下面我们看这个例子

这是L1这个语言 它对应的自动机是M1

我们把它的迁移都反转一下

再把它的终态和初态反转一下

得到的这个语言

就是它的反转的自动机

这就说明正则语言的反转

依然是正则语言

正则语言的补

如果语言是集合 集合它是要补的

那我们给了L1是正则语言

它对应的自动机

下面只讨论它的DFA了

这个DFA它的终态可能有多个

这个没关系

我们假设接受的L1的DFA是M1

另外我们将所有的终态改为非终态

再把所有的非终态改为终态

这样得到的自动机M′

这个M′接受的语言L12

这个语言刚好就是我们a1的它的补集

说明正则语言它的补依然是正则语言

我们这里给了一个例子

这个例子它的自动机是DFA

这里它的状态

把它的终态和非终态进行互换

得到的自动机就是它的补集的自动机

那它的语言就是原来的语言的补

就得到了正则语言

对于并集 连接 反转 星闭包 还有补

对这些运算都是封闭的

那现在我们还有一个运算

就是正则语言的交

正则语言a1、a2

那它们的交是不是还是正则呢

我们按前面的证明方法

就是构造它们的自动机

如果是它的DFA或者NFA能够构造出来

那当然就说明它是正则的

那现在我们已经有了前面一些运算之后

下面我们就不需要构造

这两个语言交的自动机

我们直接用一个集合的德摩根公式

或者德摩根律

那从L1、L2是正则的

我们就知道 它们的补是正则的

那它们的补是正则的

那它们得到的并就是正则的

这个并做正则

那这个语言再做补的时候

也是正则的

根据德摩根公式

这个语言 就跟这个交是相等的

所以我们就推导两个正则语言的交

依然是正则的

像这里给了这个语言

这个语言都是正则的

它们做交

我们很容易算出就等于这么一个集合

这个集合肯定是正则的

那我们就得出了正则语言对我们

提到的这几种运算都是封闭的

这节内容讲到这里

谢谢大家