Video在线视频

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

我们现在讲这一章的第三节

是正则文法和正则语言

在上一节里面我们介绍了正则文法

正则文法它就是右线性文法

或者左线性文法

正则文法 它产生的语言

实际上是正则语言

也就是说正则文法和正则语言之间

它有一个密切的关系

这个密切的关系

就是我们用这个定理来表示

我们把正则文法产生的语言

放在一个集合里面

把正则语言放在另外一个集合里面

这两个集合是相等的

那可以把定理分解为两个部分

第一个部分

就是正则文法产生的语言的集合

一定包含在正则语言这个集合里面

这也就是说正则文法产生的语言

一定为正则语言

这是我们定理的第一部分

定理的第二部分

它是这个包含了另外一个方面

就是正则语言这个集合

包含在正则文法产生的语言

这个集合里面

这也就是说你给了一个正则语言

一定能够找到一个文法

它产生的语言就是正则语言

所以我们要证明这个定理

就要从两个部分来证明

首先我们看第一部分

就是正则文法产生的语言

一定包含在正则语言这个集合里面

那我们给了一个正则文法G

它产生的语言是L（G）

要证明L（G）一定是正则语言

那怎么证明L（G）是正则语言呢

假如有一个NFA或者DFA

那产生这个语言

那这个语言就肯定是正则语言

那下面我们就说根据文法

我们能不能去构造一个DFA或者NFA

我们首先看这个例子

我给了这样的一个文法

这个文法它是一个右线性文法

它就是一个正则文法

我们希望通过它

来构造一个自动机NFA

我构造自动机的这个状态

它用一个变量来对应

首先这样 你比如它这里面 文法里面

有哪些变量呢

SAB这些变量

那我对应的这里面的NFA的状态

有S 有A 有B

那另外我还要增加一个特殊的状态

就是终态

接下来我怎么去根据这个文法产生式

来对应自动机的转移

在这个文法里面

我们给了这个自动机

首先我确定这个自动机的开始状态

开始状态 我就对应它的开始变量

这跟原来的文法是对应的

接下来我就根据它的产生式

S产生a大A

S产生a大A

S对应的是这一个状态

A对应这一个状态

那这个产生式

我就可以判断前面这一个终结符a

是它边上面或者输入符号产生的

所以这样一个产生式

我就对应了 它是S到a的

有一个变迁或者转移

这个转移它的终结符就是它的输入

这是对这样的一个产生式

我们对应状态转移

那另外一个产生式S产生b

S是这个S

b对应状态是这样

它没有对应的终结符

那我们认为它的左边

应该就是对应一个空串这个终结符

所以它对应的状态转移

就是S输入空串到b

这是这两个产生式

我们对应的它的状态转移

我们再看另外一个产生式

大A产生小a小a再b

它这个b的左边有两个终结符

这一个终结符我们好表示

那两个终结符我们该怎么表示呢

那通过前面我们扩展了

自动机里面那个方法

我可以在这个两个a这个之间

我增加一个状态

也就是我加一个状态

这个状态它就是a到这个状态

是通过输小a到达它

然后从这个状态再输a再到b

这就实现了从大A到B的一个转移

也就是通过了这一个串aa转移得到的

这是从这个产生式

到这个状态转移的一个表示

我们再看这个产生式

B产生小b大B

这个B和这个B是相同的

对应的状态

实际上它就相当于对应的有一个自环

这个自环上面是输入b有一个自环

那b产生一个终结符的a

b产生终结符a 这没有对应的变量

也没有对应的状态

那这个时候我们就把这个b

就到终态这里面就有一个转移

转移这个边上面

就是由我们输入a来产生的

那从这个文法的展示

最后得到这个自动机

实际上你看它那个机制完全是类似的

它最后到这里结束的字符串

跟这里产生的句子

你看完全是一样的

所以它们得到的语言应该是相同的

通过这个例子

总结对一般的右线性文法

我们都可以产生这个方法

你看我们假设给了G是个右线性文法

我们现在关键就是

通过这个文法构造一个NFA

这个NFA就是M

构造这个M的语言

跟这个文法的语言是相等的

那根据刚才的例子

我们构造首先通过文法的变量

来构造自动机的它的状态

通过它的产生式来构造它的变迁

那下面我们假设这里右线性文法

它的变量是V0、V1、V2

产生式因为这两类吧

要么它含一个变量

这个变量是在这个串里面最右边

也就是这种形式

要么它就是一个终结符的串

那么下面我们对这两类

怎么去构造它的产生式

首先对于这样的右线性文法

每一个变量

都对应其中的一个状态

你像刚才的变量 我们都对应了

你像变量有V0、V1、V2、V3、V4等等

这个是文法的变量

我们对应NFA的状态就是这些

那另外我们要根据刚才的例子的做法呢

我们增添一个终态

这个终态是之前V的变量

我们对应的这一个状态

这是我们自动机的状态选择

当然我们还要根据构造

增加一些新的状态

就是根据后面的需要我们再增加

像对这个产生式

Vi产生a1、a2 一直到am 这是终结符

然后Vj 这是一个变量

对这样的产生式 刚才我们的做法

就是按刚才的从Vi到Vj

有一个状态转移

这个状态转移因为

它的字符串中间有a1、a2、am

我就插M减1的状态里面

这里面分别是通过a1、a2 一直到am

在这里做了一个过度

所以把Vi最后转移到Vj

我们刚才的例子也是从这个方法做的

所以我们这个做法跟刚才的做法是一样的

只是我们对一般情况都采用这个方法

来定义它的自动机的变迁

这是对这一组产生式

下面我们再看右线性文法的

另外一类产生式

Vi它产生的是终结符的串

通过这个产生式

我们怎么构造NFA等价的

一个状态转移呢

首先是Vi这一个状态

另外我们增添了一个终态是Vj

然后在Vi到Vj之间

我们再增添m减1个状态

就是为了将a1、a2、am这些终结符串

把它从Vi转到Vj

这样我们就实现了这个产生式

跟它等价的一个状态转移

这样得到的自动机

一般的是具有这种形式的自动机

这是通过文法的产生式

我们给出了等价的效果相同的一个NFA

从刚才的构造看出来

他们的语言当然是相等的

也就是m它对应的语言

跟这个文法对应的语言是相等的

这是通过正则文法

也就是右线性文法

构造一个跟它等价的NFA

那当然这个文法的语言就是正则语言

我们也可以对左线性文法

来证明它们这个结论是正确的

这个我们只是把

一个大概的构造思想说一下

假如我们给了一个左线性文法G

我们就要构造一个右线性文法

根据这个左线性文法

去构造一个右线性文法

使得这个关系式相等

另外我们在构造过程的话

我们知道右线性文法

它对应的语言我们刚才讲了

它对应的那个自动机那个语言

它是正则的

证明了这个正则语言

根据它的性质转直接是正则的

最后证明这个G

它对应的自动机也是正则的

这样我们就实际上就证明了左线性文法

它得到的语言也是正则的

下面我们再看定理的第二部分

就是正则语言这个集合

一定包含在正则文法

产生的语言的这个集合里面

也就是给了一个正则语言

我们现在要构造一个文法

这个文法 它产生的语言

就是你给定的这个正则语言

那下面我们在证明这个定理之前

我们实际上关键怎么去构造这个文法

那给了一个正则语言

那怎么是正则呢

根据我们前面知道

一个正则语言

它肯定是对应一个DFA或者NFA

我们说对应一个NFAM

这个M它能够产生这个语言

这是正则语言它具有的一个特点

那我们再根据这个NFA自动机M

来构造这个正则文法

下面我们看一个例子

假设我们给这个语言是这个语言

这个语言大家看 是正则表示它的语言

肯定是正则的

实际上这个语言它的自动机

我们可以把它画出来

这个就是这个语言对应的NFA

通过这个自动机它的状态

我们去限定它的变量

这里面它有这样的一些状态

q0、q1、q2、q3等等

我们把它这一些状态

我们看着我们文法的变量

q0 经过输入a到q1

那我们在文法里面

就给这么一个产生式

q0 我看作 把这个状态给看作一个变量q0

它输入a到状态q1

那就是它产生的这个aq1

也就是我们上一步这类构造当中

我们把它逆回去的那种做法

就从这个状态转移 得到了这个文法

你看 它们左右是相等的

那么类似的方法

实际上我们把整个这个自动机对应的文法

都可以构造出来

那它对应的文法你比如说

可以q0产生aq1

q1它这里有一个自环

那它就产生一个bq1

q1还可以产生了这个aq2q1

通过这个自动机我们得到这类文法

那我们还可以得到了q2就产生bq3

那在这里面q3还可以产生 这是一个空串

也就是直接产生q1

另外我们必须还要考虑

对这个终态这一块呢

我们要加一个产生ε

完成了这个构造

你看这个文法它接受的串

跟这个自动机它接受的串

就完全是一样的

因此 他们得到的语言应该是相同的

那通过这个例子

也告诉了对一般的文法的构造

在自动机里面

如果有个状态q输入a

它到状态p1有个转移

那我们在文法里面

就有一个这是变量q产生ap

这在一般里面我们按这种方法

就把它对应的这个文法

就可以表示出来

这里面我们q是变量 p是变量

而这个a是终结符

根据这个状态转移里面有一个终态f

我们必须要增加一个qf这个变量

到空串的一个产生式

这样得到的文法跟自动机产生的语言

应该是相等的

它们因此是等价的

这样我们就证明了通过自动机

怎么构造跟它等价的上下文文法

实际上我们就完成了这个定理的证明

在本节当中我们介绍了

一个特殊的文法叫线性文法

在线性文法里面我们又介绍了一个

更特殊的文法叫正则文法

也就是右线性文法或者左线性文法

有这个文法它产生的语言

我们证明了它是正则语言

这个我们又找到了

正则语言的另外一种表示形式

你看到现在为止

我们正则语言

实际上有DFA可以表示正则语言

NFA可以表示正则语言

还有正则表示 它的语言也是正则语言

现在我们也证明了

正则文法也可以产生的是正则语言

好 这一节就介绍到此

谢谢大家