Video在线视频

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

现在介绍正则语言判定性质的第三部分

非正则语言的判定

在上一节里面我们介绍了泵引理

泵引理它是介绍了

是对一个无限的正则语言

它满足的必要条件

这个必要条件指

只要是这个语言是无限的正则语言

它一定存在一个正整数m

那对任意的语言当中的串

只要这个串的长度大于或等于m的话

这个串一定能够分成三个部分

x、y、z

并且满足下面这两个条件

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

y的长度大于或等于1

对任意的ixy的i次方z

都应该在这个无限的正则语言L当中

只要是无限正则语言

它是满足这个条件的

那如果不满意它

那这个语言就不是正则语言

下面我们介绍泵引理的应用

那我们泵引理用到哪呢

就是证明一个语言不是正则语言

这个泵引理刚才我们是用自然语言

把它的条件叙述出来的

那我们现在可以把刚才的泵引理

写成这个逻辑表示形式

刚才泵引理不就是说对无限正则语言

一定存在一个正整数m

对任意的一个字符串w

只要是大于或等于m的话

那这个w它一定分解为xyz

也就存在x 存在y 存在z

它满足y不等于空串

xy是小于或等于m的

这个时候对任意的k

则k大于或等于0的话

xy的k次方

z一定是L的

也就是说对于无限正则语言

这个结论是必须满足的

要证明一个无限语言不是正则语言

那就是这个结论它是不满足的

也就是我们把这个逻辑形式

它的否定形式要表示出来

那也就是这个命题的否定形式

可以表示成为这种形式

刚才这里是存在一个正整数m

那它的否定形式是任意的

对任意的正整数m

刚才是对任意的w

那我就是只要找到一个w

这个w是大于或等于m的

这个w原来是存在某一个分解xyz

存在xyz

现在这个w它任意的表示成为

xyz这三个子串

只要是y不等于空串

xy是小于或等于m的

那这个时候 我们只要找到一个k就可以了

也就是找到一个反例

使得xy的k次方z

不在这个L里面

只要是使这个逻辑形式成立的话

那这个语言就不是正则语言

从自然语言写成逻辑

从逻辑到它的否定形式

实际上大家将来学习了一级逻辑

这个表示形式是很简单能写出来的

那下面我们怎么样去利用这样的表示

来证明一个语言不是正则语言

那我们的证明步骤

根据刚才的这个否定形式

我们翻译成为自然语言

就是第一 选取一个任意的正整数m

第二个 找一个长度至少是m的这一个串

这个串当然是属于这个L的

再然后把这个w任意的分解xyz

这xyz是任意的分解

当然它必须要满足y不等于空串

xy是小于等于m的

不论怎么写

只要是满足这两点就可以了

最后我们去找一个k

也就是相当于找一个反例

使xy的k次方z 不在这个语言里面

只要是把这个（05：37）完了

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

就根据我们刚才的泵引理

下面我们看一个例子

证明语言

这个语言是我们比较熟悉的

0的n次方

1的n次方

也就是0出现n个之后

1也出现n个

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

那根据刚才的泵引理

首先对任意的正整数m去写一个w

因为我们要求w长度是大于等于m的

而且是属于这个语言里面的

那我们就选取0的m次方

1的m次方

所以我们在选取这个w的时候

是你证明这个结论当中非常关键的一步

这个w它的长度肯定是大于或等于m的

那现在我们把这个w写成xyz的形式

w等于xyz

当然我们这个y是不等于空串的

xy是小于或等于m

只要满足这两个条件

你xyz 不论是怎么选取

任意的

那大家可以看出

只要是xy小于或等于m的话

因为这个w前面0的个数是m个

那这说明了xy它全部都是字符0

全部都是字符0

另外 y是不等于空串

那就说明y它含0的个数

肯定是大于或等于1的

那么我们现在选取xy的k次方z的时候

我们把k就取成0

k取成0

实际上就是把y 就取成空串了

那就是xz

xz我们知道y的个数

含0的个数

是大于或等于1的

那xz那就看出 它这个串当中的

因为把y取出了

那这个0的个数 就比1的个数就少

这就说明xz它就不可能满足

0的个数和1的个数是一样多

因此k等于0的时候

也就是xz它不属于这个语言L01当中

这样我们就通过泵引理严格证明了

这个语言就不是正则语言

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

我们刚才讲了在正则语言这个集合之外

这个语言v

v的R次方

这个也就是叫v∈

这个语言我们说

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

它也是非正则语言

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

怎么证呢

首先这个语言它是无限的

大家看这个语言它不会是有限语言

是无限的

我们就可以用泵引理

那用泵引理 按刚才泵引理的步骤

首先要对任意的正整数m

我找一个字符串

找这个字符串要∈这个L当中

并且这个长度是大于或等于m的

那这个选取 大家看看

既在这个L当中

长度有大于等于m

那我们选取的话

就可以选取这类的字符串

就令这个W等于a的m次方

b的m次方

这个a的m次方 b的m次方

也就是我们的v

那它的翻转就是b的m次方 a的m次方

这个字符串肯定是在L当中

它的长度应该是4m

它是大于m的

所以这个字符串是满足我们的选取条件的

现在把这个w

我们就表示成为xyz

任意的xyz

只要满足下面这两个条件

y是不等于空串

xy的长度是小于或等于m

只要满足这两个条件

xyz任意的选取

那这一选取你看

这个xy它是小于或等于m的

而a的个数因为a这个子串

是在这个串当中是前缀

它有m个

xy是长度是小于等于m的

那就说明x和y 它们全部都是字符串a

再还有y长度是大于或等于1的

就说明y含a至少要含一个a

我们就可以把y

就可以表示成为a的k次方

k是大于或等于1的

k它不可能等于0

因为我们刚才构造的y

它是长度大于或等于1

因此这个w表示串xyz就可以表示成

这样的串 因为这是a的m次方

接下来是b的m次方

b的m次方

a的m次方

那我们现在就看前面的xy

证明xy都是a

而且y的个数是大于或等于1的

所以y就在这前面a的这一部分里面

也就是y等于a的k次方

对于这个字符串里面

我们把y的i次方里面

我们把i就取2

就看我们字符串xy的2次方z

xy的2次方z

实际上就是在这个y后面再增添了一个y

也就是a的k次方

那这样 大家看

这个字符串实际上就是

前面a就成了m加k个a

再是m个b

再是m个b

然后是m个a

这个字符串xy的平方z

那从这样的一个结构

我们看看就成了a的m加k次方

b的m次方

b的m方

a的m次方

因为L是一个回文也是vv的R次方

这是一个对称的形式

而这种表示大家看

它在（13：57）这形式了

因此 这个串就不属于L

不属于L

根据我们的泵引理

就说明这个L不是正则语言

这节里面我们介绍了

怎么利用泵引理来检验一个无限的语言

不是正则语言

好 这节内容介绍完毕

谢谢大家