当前课程知识点:软件理论基础 > 第十章 下推自动机与CFG化简规范 > 10.7 CFG的化简与Chomsky范式 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍CFG化简与规范的第四节
CFG的化简与Chomsky范式
在这一章里面主要是介绍
上下无关文法的化简
介绍步骤是首先消除无用符号
然后消除ε产生式
再消除单一产生式
这样的化简之后 发现还会出现一种符号
把刚才的步骤稍稍的调整一下
对这样给出的上下无关文法
第一步 我们就消除ε产生式
然后再消除单一产生式
最后消除无用符号
我们注意 第一步消除ε产生式之后
这个文法再不含有ε产生式了
那你在第二步 第三步 你在做的时候
再不会出现ε产生式了
第二步你消除单一产生式
没有单一产生式了
在你的第三步消除无用符号的时候
它就不会再增添新的单一产生式
所以这样的步骤
它得到的文法就不含ε产生式
也不含有单一产生式
也不含有无用符号
这个化简的步数非常重要
通过这个化简 我们得到这样的定理
给了文法经过上面的三步化简
我们得到的文法
新的文法记为G1
这个G1它就不含ε产生式
不含单一产生式
也不含无用符号
新的文法跟原来的文法
最多只相差一个ε这个空串
下面我们介绍一类特殊的上下无关文法
称为Chomsky范式
Chomsky范式它是这样的上下无关文法
首先这个文法它是不含无用符号的
下面这个文法的产生式只有两类
要么它右边是两个变量
要么它右边只是一个终结符
这样的文法它不含无用符号
它也没有ε产生式 也没有单一产生式
这类文法 我们把它叫做Chomsky范式
这个文法的形式非常简单
大家可以看 因为只含有这样两类的
它的产生式
这个文法 它的语法分析树大家很清楚
它就是一个二产生式 非三简介
我们看一个例子
这个文法它就满足我们Chomsky范式的要求
它就是Chomsky范式
而这里给了一个文法
这个文法里面
右面这么一个关系式
它不满足Chomsky范式
这个关系虽然它是终结符
但是它是两个终结符
它也不满足Chomsky范式的要求
所以这个文法不是Chomsky范式
给了一个上下无关文法
它怎么去转化为Chomsky范式
转化的步骤
第一个步骤 对任何一个不含空串的这个
上下无关语言
一定是存在一个上下无关文法的
首先对这个文法 我们转成Chomsky范式
这个转化 因为刚才给的Chomsky范式里面
它是不含无用符号
它的产生式只有两类
它就不含ε产生式
也不含单一产生式
那前面的步骤也进行化简
首先消除ε产生式
再消除单一产生式
最后消除无用符号
这就是按我们上一节讲的内容
把它进行化简
这样得到的这个文法里面
它就不含无用符号
不含ε产生式
也不含单一产生式了
但是这里面产生式
它可能不满足Chomsky范式的要求
第二步 对G2这个文法
就是做这样的变换
第一个变换是假如它的产生式的右边
是含终结符
但是终结符的个数多于一个
我就要引入一些新的一些变化
那我引出一个变量A
A产生小a
这个产生式
对其它的终结符我类似的定义
它是终结符这一个
要么它全部都是变量
就化成了这种形式了
它右边的长度是等于2
那是满足Chomsky范式了
那右边的长度是大于2的时候
那比如说A产生B1B2Bk
这个k是大于2的
这个级连的方法就是
引进k-2个变量
C1、C2、Ck-2
就把刚才这个产生式
增加这样的一些产生式
A产生B1C1
C1产生B2C2等等
移到Ck-2产生Bk-1Bk
这样的一串的方法
得到的效果跟这是一样的
但是下面这些产生式
它是满足Chomsky范式的
得到了这个新的文法G1
G1就是Chomsky范式
而且G1它的语言 跟我们开始文法的语言
它是相等的
下面我们看这个例子
这是我们之前讲过的
下推自动机转上下无关文法的例子
经过了消除无用符号
消除ε产生式
消除单一产生式 达到这种文法
我们发现了就刚才那些步骤
它会产生新的融入的符号
这个融入符号就是D和A
我们消除这个无用符号之后
得到新的文法就是下面这个文法
这个文法不含ε产生式
不含单一产生式
也不含无用符号
但是这些表示的产生式
它不是标准的Chomsky范式
所以我们首先引进一个新的变量A
A产生0
文法就表示成为下面这种文法
在这个文法它的右边要么是单个终结符
要么是变量的话
它就变量就是两个或者多余两个的
只有两个的 那是满足Chomsky范式
对于多余两个的 ABC
我就采用前面介绍的级连的方法
引进一个变量D加这个文法
就化成为这个关系式
这个就是一个标准的Chomsky范式了
这样我们就把前面那个上下无关文法
就转化为一个Chomsky范式
那下面我们有这样的定理
对任何的一个上下无关文法G
通过上面的这些步骤我们构造的文法G1
这个G1就是Chomsky范式了
它满足这个语言跟原来的语言
最多只相差一个ε空串
这章里面 我们介绍了上下无关文法的化简
我们要消除ε产生式
消除单一产生式
消除无用符号
前面这个化简方法的确是能够有效的
对文法的变量和无用产生式进行化简
之后我们还介绍了Chomsky范式
Chomsky范式是一种
结构非常好的上下无关文法
在下一章里面
我们还利用这些结论
要讨论上下无关语言的一些性质
好 这章内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试