Video在线视频

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

现在介绍正则语言判定性质的第三个方面

非正则语言的判定

前面我们已经讲过了

非正则语言的判定方法 就是用泵引理

泵引理可以判定一个无穷的语言

它不是正则的

我们前面也讲过了几个例子

为了同学们加深对泵引理的理解和应用

我们下面继续介绍几个例子

首先 我们看这个语言

这个语言是a的n次方

b的i次方

c的n加i次方

也就是这个语言的它的输入字母是abc

a首先是出现n个

然后b是再出现l个

c是a和b的个数之和

那这个语言大家看

因为n和l是任意的整数

那这是一个无限的语言

这个语言我们说它在正则语言之外

它不是正则的

我们可以用泵引理来判定

我们证明这个语言不是正则语言

那根据泵引理的证明方法

对任意的正整数m

我们现在要取L上的一个字符串w

w它必须是大于或等于m的

m是任意的

那大家看 要设入这个语言L

而且它的长度要大于等于m

我们在上一节我们讲过

取这个w是非常关键的

那大家看看

我们选取什么样的字符串既属于它

又长度大于等于m呢

有经验的同学可能就马上知道

我们只选出这个字符串就OK了

a的m次方

b的m次方

那c是a的个数和b的个数之和

那就是2的m次方

那这个字符串大家看

它应该在L当中

而且长度是明显是大于或等于m的

因为它的长度是（4m）

那在这个字符串

我们现在把它写成为xyz

任意的写

xyz这个字符串只要是满足下面两个条件

一个是xy它的长度小于或等于m

y的长度大于或等于1

只要满足这两个条件

这个xy任意的

那这一写的话 大家可以看出

因为前面这个字符串a的m次方

表示它的前缀

a是含m个

那xy的长度小于或等于m

说明xy它必须都是取字符a

从这个条件可以看出这一点

那下面y是大于等于1

实际上就可以表示成为y等于a的k次方

k是大于或等于1的

那这个字符串xyz实际上就表示成为

这是m个a

m个b

2m个c

起初这xy它是在a当中是取值的

是a的某一部分

那在xy的i次方z

这个里面取值 特别是i取0的时候

也就是在原来字符串当中 这个y

y的i次方就取值空串

在这个字符串当中 就去掉了k个a

那这个得到的字符串就是m减k个a

m个b

2m个c

那这样的字符串

实际上就是等于a的m减k次方

b的m次方

c的2m次方

那这个字符串是不是在我们的

前面的L当中

前面的L实际上是a的n次方

b的i次方

c的n加i次方

也就是c的个数

是a的个数和b的个数之和

那我们再看这样的字符串

a的m减k

b的m

它两个个数加起来是2m减k

它是不等于2m的

因此 这个字符串是不在L当中的

这就说明前面给的这个语言

不是正则语言

这是跟泵引理来证明的

下面我们再看一个例子

这个语言输入字母是a

它是a的n的阶层次方

n是大于或等于0

我们说这个语言

它也不在正则语言这个集合里面

那下面我们怎么样证明

这个语言不是正则语言呢

因为这个语言是无限的语言

根据前面几个例子

我们就用泵引理

泵引理 我们的证明方法来跟前面很类似

对这个语言 我要对任意的整数m

要写一个这个语言里面的w

这个w长度是大于等于m的

大家看 我怎么样去选取这个w

根据前面几个例子的经验

那我们要选取的话 这个很简单

我们就取w等于a的m阶次次方

那我们的这个字符串 把它写成为xyz

只要是满足xy它的长度小于或等于m

y的长度大于或等于1

任意的xyz

y因为长度是大于或等于1

就可以写成为y等于a的k次方

那xyz已经是a的m阶次方

可以表示成为这个串的形式

因为它都是a

因为整个m是我们任意一个正整数

我就把这个阶层首先我分一个出来

下面来构造的时候

在y的i次方

i我就取2

我们看看这个时候

字符串就可以表示成为xyy

就在原来的这个字符串里面

增加了一个y

也就是a的k次方

那这个字符串就变成了m加k

在后面还有一个m阶层减m

那大家看看这个字符串

是不是具有a的m阶层

或者是p的阶层这种形式

下面看这个字符串

是不是属于这个语言L

因为这个语言是表示成为a的阶次方

如果这个字符串

具有这个语言的表示形式

也就是输入这个语言L的话

那就是一定存在一个p

这个m阶层加k就等于p的阶层

m阶层加k是不是具有这种形式呢

下面我们定义我们m是大于1的

而这个k呢

因为我们刚才选取的时候

大家可以看出

xy的长度 是小于或等于m的

所以k它是小于等于m的

m的阶层加k

我把它就扩大

把这个扩大为m

这就小于或等于它

然后再把这个m扩大成m阶层

因为m是大于1的

所以是（09：56）它小于它的

那这个表示式 我提取公因式

实际上它就表示成m加1的阶层

也就是说m的阶层加k

它是小于m加1的阶层

当然它是大于m的阶层

这就说明了m的阶层加k

它不是一个阶层的形式

也就是它不可能写成p的阶层

这里就说明刚才给的这个语言L

就不是正则语言

这是我们给出的第二个例子

下面我们再看一个例子

证明字符

输入字符是零 p为素数

这个语言是0的p次方

就是任何的素数为子数

这个语言 我们说这个语言

它也不在正则语言这个集合里面

它是非正则语言

根据代数的一些知识

我们知道因为素数是无穷的

因此这个语言它是一个无限语言

那我们要证明这个语言不是正则语言

下面我们也是用泵引理来证明的

那对于这个语言

选取任意的正整数m

这个跟前面的方法一样

因为这个数是无界的

我就选取这个p是大于或等于m的

因为它是素数无界的

那w就表示成0的p次方

也就是w属于L

而且长度是大于或等于

你这个任意的正整数m的

这是我们前面一直是这个做法

下面我的这个w写成xyz

任意的写

只要满足y长度是大于或等于1

这个xy的长度小于或等于m

我们把y就写成为y的j次方

因为y的长度大于或等于1

这个j它就是大于或等于1

小于或等于m

我的这个j下面用它

来构造我的y的k次方

怎么构造

我就取k就等于刚才那个素数p

再减去那个j

那再减去 大家看

它肯定是大于或等于0的

再看xy的k次方z

这样一个串 也就是y 它重复了k次

这个k就是p减j

我们通过这样一个简单的推导

这个推导就是非常简单的一个代数推导

就发现了实际上这个数字

就可以表示成为0的这个指数是

ja加1乘以p减ja

也就是说这个指数它就不一个素数了

那这样就说明这个语言

就不是正则语言

在这章里面我们主要讨论了

正则语言的一些判定性质

特别是我们讲到了

怎么判定一个语言不是正则语言

这是用了泵引理

我们要说明一点

这里判定正则语言的它的条件

不是充分条件

它是一个必要条件

我们给出一个反例

这个反例就说明这个语言

它是满足泵引理下面的这些条件

我们可以找到一个适当的m

它满足我们泵引理那个条件

但是这个语言大家看

它实际上不是正则语言

这就说明泵引理是判定正则语言的

它的必要条件

不是充分条件

正因为这样一个必要条件

我们才能够证明一些语言不是正则语言

好 这章内容介绍完毕

谢谢大家