当前课程知识点：软件理论基础 > 第七章 上下文无关文法和推导 > 7.4 规约、推导和语法分析树之间的关系 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍
上下文无关文法和推导的第四节
就是规约 推导
和语法分析树之间的关系
在前面两节当中我们介绍了
上下无关文法
它可以推导出一些字符串
这个推导的方法有规约
有推导 还有语法分析树
那它们之间有些什么关系呢
我们有下面这么一个命题
给了一个上下文无关文法
下面这些命题是等价的
第一个字符串W
这是终结符构成串
它可以归结到变量A
这是一个命题
A可以若干步能够推出W
A可以若干步最左推导 推出是W
A可以若干步最右推导 推出W
还有存在一个
以A为根结点的语法分析树
它的产物就是W
这五个命题它们相互之间是等价的
五个命题证明它们相互等价
你这个排列组合的话要证明很多步
我们采用另外一种证明方法
首先我们从第五个推理
能够推出这个语法分析树
那从语法分析树得到最左推导
也可以得到最右推导
当然最左推导和最右推导
它们都是推导
那以它做前提
可以得到推导
那从这个做前提
可以推出这个递归推理
我们只要证明了这样一个环
实际上就证明了
这五个命题它们是相互等价的
那么我们下面来做一证明
首先是从规约到语法分析树
也就是说给了一个上下文无关文法
这个串W
它能够规约到变量A
那一定存在一个
以A为根结点的语法分析树
它的产物就是W
我们要证明这个结论
通过对规约的步数作归纳
如果这个规约 一步它能够规约出来的话
实际上它就有这么一个产生式
那这个产生式
实际上它就很容易
搭建一个这样的语法分析树
这就是结论很明显的
假如 它的规约步数是大于1
考虑最后的一步的
它的规约用了这个产生式
因为它的规约的话
都是用产生式来做规约的
最后用了一个这个X1、X2、XK这个串
规约到A
那从这个产生式
我们实际上
就得到这样的一个子数了
它们的叶结点分别为X1、X2、XK
这个规约它是从W规约到A的
下面分别对应的是W1规约到X1
W2规约到X2等等
又到WK规约到XK
这个规约的步数在整个这个规约来说
它是少了一步
我们可以用归纳假设
那就存在这么一个指数
以X1为根结点它的产物是W1
以X2为根结点产物是W2
以XK为根结点它的产物是WK
这样不就达成了一个以A为根结点
它的产物是W1、W2、WK构成的
也就是我们的W
这个结论就这样可以证明出来
下面我们再看从分析树到推导
存在一个语法分析树 它的根结点为A
产物是W
那它一定存在这样的推导
A推导出W 或者A最左推导出W
或者A最右推导 推导出W
我们这里这个证明这些推导
我们只证一个这种推导
就是A这种推导出W
对语法分析树 它的高度我们做归纳
如果是语法分析树的高度为1的时候
A当然很容易得到它的最左推导
能够推导出W
因为它只有这一个产生式
那假如这个语法分析树的高度是大于1
我们看第一个结构
它肯定是有这样一个产生式
A产生X1、X2、XK
但从这里我们就分别可以得到
X1的产物是W1
X2的产物是W2
XK的产物是WK
这里面树的高度
它就是叫整个这个树的话
它是高度减1
X1假如它的产物是W1
那我们通过关类假设
X1一定能够推出W1
类似的X1能够推出W2
XK一定
应该说还是最左推导推出WK
那我们通过这样的归纳
我们就可以得到通过这个A
能够最左推导 能够推出这个W
这里就是利用归纳就会得出我们的结论
下面我们再看从推导到规约
假如从A能够推导出终结符串W
那在这个W一定能够规约到A
那下面我们就对这个推导的步数做归纳
这个跟我们前面
整个证明思路是很类似的
如果是这个推导步数为1的话
这一步能够推导出来的话
那它就是用了这个产生式吧
这个规约当然是很显然了
那如果推导的步数是大于1
你看它第一步的推导
第一步的推导一定用了这个产生式
再然后再推推推 推导出W
那从X1能够推出它这样一个子串
X2推出子串
我们分别把W对应着X1、X2、XK
分成W1、W2、WK
当然Wi可能等于Xi
也可能是Xi推出W
不管是哪一种情况 这个推导的步数
它比原来的步数是少一步的
那么我们就可以用归纳
X可以推出W
W就可以规约到X
因为就是步数较之前少一步
我们就用归纳假设
这样我们就证明了所有的结论
因为我们证明的是采用了这样一个循环
所以我们刚才的这种方法就证明了
这五个命题它们彼此是等价的
这节我们讨论了规约 推导 语法分析树
它们之间的关系
这种关系实际上它们是等价的
以后我们在分析我们的文法
它产生的树型或者句子的时候
用哪一种实际上都是一样的
好 这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
