Video在线视频

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

现在介绍上下无关文法的应用

与文法的二义性的第六节

上下无关文法构造实例

我们看看这个例子

构造一个上下无关文法

它满足这个语言

这个语言是输入字母是0，1

这个串当中0的个数

和1的个数是相等的

这个语言就比之前给的那个回文的语言

就复杂一些

因为这个0和1它没有次序的要求

只有个数的要求

一般的想法我们可能是这样想

你有一个0 就有一个1

那我们就把所有0和1出现的可能性

这里010101101010

估计它有可能的只有这些

再把s加到它不同这个位置

那这样是不是就可以得到这个语言呢

这生成了这个语言

它肯定是满足0的个数跟1的个数

它应该是相同的

但是它不一定是满足这样的语言

我们下面看看这个串00111100

这个串它应该在这个语言里面

你要是用这个文法它就生成不了

所以这个文法

它不是满足这个语言的文法

也就是说这个文法是不正确的

那怎样描述

该语言的一个上下无关文法呢

那我们下面看另外一个方法

因为W它这个串

你要求它0的个数和1的个数是相等的

那它开头可能是0 也可能是1

如果开头是0的时候

那在某个位置一定有一个1

0和1这个之间

它有1个或多个0，1的对

在这个1之后

也应该有0和1的一个或多个的对

我们根据这个特征 就可以写一个文法

那如果对于开头是1的时候

这个构造方法是类似的

根据刚才的分析

我这个文法就这样写

开头是0的时候

一定有一个1

在0和1当中有一个或多个0，1的对

在之后也应该有一个和多个0，1的对

那如果开头是1的

一定有一个0

在1和0之间

这个0，1的对 有多个

在之后也应该有多个

S可以等于空串

我们可以看出这个文法的语言

肯定是在我们给定那个语言里面

也就是说它描述的串 一定是满足

0的个数和1的个数是相同的

有的串是使用这个L的

这个文法没法去描述

我们要证明另外一个包含关系

要成立的话 那这个文法

就是我们需要的这个文法

那我们要证明这一点的时候

就根据这个语言当中串的长度做归纳法

如果串的长度是等于0的时候

因为在我们的文法里面

是可以产生空串的

所以这一点 是很容易验证

空串是使用这个文法的语言

如果是假设

串的长度小于或者等于2n的时候

对这个串属于a2

一定在这个文法里面

从开始变量能够推导出w

这是我们的归纳假设

那当这个串的长度

假设是2倍的n+1的时候

要证明刚才的文法

也一定能够推出这个v

那v是属于L

它是01构成的

开始一个符号

它可以是1 也可以是0

那如果是0的时候 这个v等于0w

w这个时候 它的长度应该是2（n+1）

也就是0的个数为n个

1的个数为n+1个

这刚好就符合我们前面介绍的引理了

那这个时候根据引理结论

一定存在一个1

这个w可以写成为α1β

其中α 0的个数和1的个数是相同的

β 0的个数和1的个数也是相同的

而且α和β它的长度

都是小于或等于2n的

那这个时候就可以用归纳假设

归纳假设就是一定存在这样的一个推导

从开始变量

能够推导出α在这个文法里面

也存在这类推导 从开始变量能够推导出β

在我们这个文法里面

我们用第一个产生式 S推出0S1S

然后用归纳假设 这个S可以推导出α

也就是0α1S

再用我们的归纳假设 S可以推导出β

那这就是 也就是从这个式子可以推出0α1β

这个关系式就是我们的v

也就是对这种形式的串

我的确能够在这个文法里面

从开始变量能够推导出它

那假如第一个符号是1的时候

我们这个推导完全类似的

也能够从开始变量能够推出为1的时候的它

说明我们给定或者构造这个文法

的确是产生这个语言的文法

下面我们再看一组方法

我们也是要构造

产生0的个数和1的个数都相同的这个语言

它的上下无关文法

我们采用这种方法也可以

对于任意的字符串

在这个文法里面有三种情况

首先0的个数和1的个数是相等的时候

我们用S来产生

但如果是0的个数比1的个数要多一个的话

我用这个A的这个变量产生

还有一种情况就是

如果0的个数比1的个数

要少一个的话

我通过变量B来产生

大家也可以去证明

刚才这种文法产生的语言

也是我们给的那个语言

下面我们再看一个例子

这个例子

是要构造一个上下无关文法

它接受的语言是这样的语言

字母表示0，1

这个串它作为0的个数

是1的个数的两倍

刚才给的例子是0的个数

和1的个数是相等的

现在是0的个数是1的个数的两倍

这好像比那个问题要复杂很多

我们采用我们刚才的构造文法的方法

类似的我们可以得到这个语言的文法

因为它是0的个数是1的个数的两倍

那我就可以把0和1

写成为这几种可能

001，010，100

然后再用刚才的那个方法

把所有可能都考虑进去的话

我们得到的文法就是这样的

大家可以下面去证明一下

这样的文法是不是这个语言的文法

这实际上这个文法产生的语言

肯定是0的个数是1的个数是两倍

那反过来是否成立

实际上我们关键是要证明另外一方面

对这个例子

我们还有一个解法

这个解法我们构造的文法是这样的

它产生的语言

也是0的个数是1的个数的两倍

下面我们再看一个例子

这个输入字母是ABC

语言是a的i次方

b的j次方 c的k次方

要求i不等于j

或者是j不等于k

那么给的这个语言

要设计一个上下无关文法来解释它

这个语言它的特点就是 abc是有次序的

首先是a 然后是b 最后是c

abc的个数是不同的

要设计a的个数跟b的个数不一样

就必须要把a的个数跟b的个数

是一样的 事先考虑出来

然后再考虑他们不一样的

这就要么a的个数比b的个数多

要么a的个数比b的个数少

那我们设计的时候

我们就这类文法来给出来了

这个文法实际上它主要这个特点

A是生成0个或者是多个A

B是生成0个或者多个B

C是生成0个或者多个C

那然后在生成了这个B和C的个数

是不等的 是用B1来生成

首先是生成它们相等的 使用这个产生式

然后如果是B的个数

跟C的个数要多的话

我到这个产生式

如果是C的个数比B的个数多

我就用这个产生式

这个是用B1生成

B的个数跟C的个数是不同的

A的个数跟B的个数不同的话

我用B2来生成

这个生成方法跟这个方法是一样的

最后我们就得到了S要么生成AB1

要么是B2C

这个文法就满足我们那个语言的要求

下面我们再看一个例子

这个例子里面给的语言 输入字母还是A，B

只是它构成的串是这样的形式

构成的串它是不能够写成

WW这个形式的字符串

我们要构造一个上下无关文法

来解释这个语言

这个是重复的W

就不能够写成它

如果串的长度是奇数的话

它一定不能够写成WW

那怎么样去描述一个输入字母是ab

长度为奇数的这类文法呢

我奇数用O 它产生COC

C它是要么产生a 要么产生b

那下面我们看长度是偶数的

也不能写成这样的

我们该怎么去做呢

下面我们分析一下长度为偶数的串

我们假设长度为2n

2n它可以分成为两个奇数的子串

一个是以i为中心

一个是以n+i为中心

下面我们看

这个例子

假设这个串长度是为20

20前面这个子串是10个

后面子串是10个

比如说我分成以2为中心这个子串

还有一个是n+2

那就是12为中心的

这个为中心或这个中心

它们的半径分别为

这为半径

构成的这个串刚好就是从a1到a2这个串

那只要这个a2和a12这两个不同的话

它们就一定不能够写成WW

那怎么样去描述刚才两个奇数的子串

它们中心不同的

那么我们就可以采用这类文法

这个文法呢

用这些变量S

它要么产生长度为奇数的串

要么产生长度为偶数的串

长度为奇数的串 我们刚才说了

它可以用这样的描述

这个是不能够写成ww的

如果是长度为偶数的串

长度为偶数的串

它可以分成两个奇数串的连接

一个是a 一个是b

a为奇数的串

这个串它由A来产生的话

那A产生CAC

它的中心是a

另外由B产生的是CBC

中心为b

两个中心一个是i 一个是n+i

两个一个是a 一个是b

它两个不同

因此 它这两个产生的这个串

是不能写成WW的

这是前面它的中心为a

后面中心为b

它不能表示为WW

那对称的 我们还可以前面的中心为b

后面的中心为a

也就是把这个1产生ba 这里表示出来

得到它另外一个表示形式

那它也是不能够写成WW的

所以根据这个分析

我们这个文法

就得到了它的变量是ABCEOS

它的输入字母是ab

开始变量是S

产生式是由这个构出来的

这样得到的文法

它的确能够满足

我们前面的那个语言的文法

今天我们介绍了上下无关文法

它的应用以及文法的二义性

我们讲了上下无关文法的一些构造方法

通过这些内容的学习

大家对上下无关文法

有了更深层次的认识

好 今天的内容讲到这里

谢谢大家