当前课程知识点:软件理论基础 > 第六章 正则语言的性质与DFA优化 > 6.4 非正则语言的判定 2 > 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
它满足我们泵引理那个条件
但是这个语言大家看
它实际上不是正则语言
这就说明泵引理是判定正则语言的
它的必要条件
不是充分条件
正因为这样一个必要条件
我们才能够证明一些语言不是正则语言
好 这章内容介绍完毕
谢谢大家
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试