当前课程知识点：软件理论基础 > 第八章 CFG的应用与文法的二义性 > 8.5 CFG的构造方法 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍上下无关文法应用
与文法二义性的第五个内容
就是上下无关文法的构造方法
那怎样去设计一个文法
来满足或者实现这个语言
是我们在这门课当中需要解决的问题
也是同学们需要掌握的这个能力
给了一个上下无关语言
要构造一个文法
这个工作往往是不太容易的
文法的构造
它没有一个统一的一个解法
给的语言是正则语言的话
你要构造它的正则文法 这些比较简单
但是对于上下无关文法 它就困难得多
一般的我们要考虑文法的
它的递归的一个结构
我们要定义一些变量
这些变量要保证你实现你的语言这个功能
你要保证这里面递归它的完整
还要保证它的终结
这就是我们在上下无关文法里面
它的构造它的难度
我们下面看几个具体例子
这个语言大家之前应该见到过
构造它这个文法
我们只需要这样的一个文法表示
S产生0S0
要么S产生1S1
要么S产生0
也是中间那个0
要么S产生1
或者S产生空串
这样得到的语言 它一定是对称的
所以这个文法就很简单
那么下面再看另外一个例子
构造文法要满足这个语言
这个跟刚才这个语言来比呢
它也是对称的
但是它们之间还是有一点小差异
这个文法是S产生0S0
或者S产生1S1
要么S为空串
这样产生的语言
它的长度一定是偶数的
那相比这个语言 跟刚才那个语言
它们构造的这个语言
实际上包含了这个语言里面
它少了中间的为0或中间为1
这么一个集合
这两个语言要构造的文法比较简单
编程也很简单
那下面我们再介绍稍稍复杂一点的
这个文法的构造
在介绍之前
我们先讲一个引理
这个引理是如果有一个这个0,1的字符串
它有n个0
有n+1个1
那么一定存在一个1
它就把这个字符串分成前后两个部分
前面是α 后面是β
α和β 它的0和1的数量是相等的
因为我们整个这个串当中
1的个数比0的个数是多一个
实际上这个引理证明方法也很多
我们可以用归纳法证明
下面我们采用另外一种证明方法
这个w因为它是2n加1的长度
我们设它为a1，a2
a的2n+1
每一个字符要么是0 要么是1
这里面因为它是1的个数是n+1个
0的个数是n个
第一个元素a1
a1如果是等于1的话
那w实际上就写成了1β
1β实际上就是我们要求的这种形式
因为1的前面可以看作一个空串
后面这个β
后面这个β一定是
0的个数跟1的个数都是相等的
所以这个时候这个结论是满足的
那如果是a1是等于0的时候
就构造一个复杂函数f
这个f它满足什么呢
f（0）是等于0
那对于这个下标1、2 等等一直到n
我们定义了如果ai是等于0的时候
它就减一个1
f（i） 如果是ai等于1的时候
它就加一个1
实际上这个f这个函数
它是1的个数跟0的个数的一个差
满足fk
fk就是下标
它是等于1的个数
减去这个α当中0的个数
α就是这个串
我们看f（k）还有一个特点
就是f（k）+1和f（k）之间它不可能相等
它之间要么多一个1 要么少一个1
再我们还注意
因为我们刚才假定a1是等于0的
a1是等于0的
就表示f1是等于负1的
你1的个数比0的个数要多一个
所以f（2n+1）是等于1的
有了这样一个条件
它们之间要彼此是不可能相等的
初值f（1）是等于负1
最后一个是等于1
实际上我们就得到了它一定存在这个k
这个k是在ak是等于1的
f（k）-1是等于0的
f（k）是等于1的
可能这里k有很多个
我们只找满足这个条件当中
最小的一个k
就把这个从1到k-1
这样的一个子串去找α
0的个数跟1的个数
因为f（k-1）是等于0的
就说明它们是相等的
那后面那一部分就记作β
那β里面的
0的个数跟1的个数也是相等的
所以我们这样就证明完了
有了这样一个定理
我们就可以解决一些复杂的
一些文法的构造
我们看一个实例
这一个串根据刚才的
我们给的那个f（n）的构造
得到这样一个图
这个图里面分别是a1、a2、a3、a4、a5、a6
一直到a11
开始一个是0
这个我们刚才说的a1是等于0
a等于0那是负1
a2也是等于0
那再负一个就负2了
a3是等于1 这个时候它就加一个1
再f（3）就等于负1了
a4等于0
它又减一个1
a5是等于1 它加一个1
a6是等于1 加一个1
a6这一部分 f（6）是等于0的
它可能还不一定满足
我们开始写的那一个k
我们看后面
后面a7的时候 发现a7这是0
这里不是1
这个时候不是我们要找的那个k了
它这里面又减了一个1
到a8的时候
a8的时候是等于1
是f（8）是等于0了
f（9）这个时候
我们f（9）是等于1了
这个时候我们发现
这个9是我们要找的那个k
前面从1到8
就是a1到a8就是我们要找的那个α
这个k值是等于9
k（n-1）等于8
则α是等于这个子串
这个子串里面0和1的个数它是相等的
有了这个定理
我们刚才讲了可以构造一些
比较复杂的这个文法
这是我们下一节要介绍的
好 这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
