当前课程知识点：软件理论基础 > 第十章 下推自动机与CFG化简规范 > 10.5 消除e产生式 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍上下无关文法的化简与规范的第二节
消除ε产生式
就是为了文法的设计和规范
我们看ε产生式它
在我们的文法里面
可能这个语言要产生空串
其他的它不会改变的
所以我们消除ε产生式
对除了ε以外
其它没有任何影响
像ε产生式我们要计算一个叫可空符号
什么是可空符号
在这个文法里面给了一个上下无关文法
假如变量a它在这个文法里面能够推出ε
我们就称这个A为可空符号
要消除ε产生式
就必须要计算可空符号
那可空符号怎么计算
假设给了一个上下无关文法
我的可空符号
是根据下面的这个递归算法得到的
首先如果有A产生ε这个产生式
那我们说A就是一个可空符号
如果有这类产生式B产生C1C2Ck
这一串字符串
而每一个Ck都是可空符号
那我们就称这个B也是可空符号
通过这种算法
就可以得到G的所有的它的可空符号
而且恰好得到它
通过这个算法它得到的符号都是可空符号
另一方面 任何一个可空符号
都可以通过这个算法得到
这里我们就给出了可空符号的一个计算
我们是通过下面的步骤
来消除这个ε产生式的
第一步要计算这个文法当中的
所有的可空符号
对每一个产生式 A产生A1A2Ak
假如有一个符号它是可空的
它就按出现或不出现两种情况
我们就把一个产生式
就变成两个产生式了
这个可空符号
那我们假设这个里面有m个可空符号
m如果小于k的话
小于这个所有的变的个数
实际上按刚才
每一个可空符号可以变两个
这样的一个产生式
就可以变成2的m次方这么一个产生式
那如果是m等于k的话
这里面会多出一个ε产生式可空符号
我们只得到2的k次方减1个产生式
新的文法里面
这个G1里面不含G的所有ε产生式
这样的文法实际上就不含可空符号
而且文法跟开始的文法之间的语言
几乎是等价的
就是稍稍有一点差异
我们用下面的定理来描述
就是通过上面的算法
我们构造的这个文法G1
这个G1 它就不含ε产生式了
那G1的语言跟原来的语言
最多就相差一个ε这个空串
要证明这个定理
我们就证明了
S在G1当中推出W
当且仅当 S在G1当中推出这个
这个呢 大家可以回去看一看 验证一下
下面我们看这个例子
这给了一个上下无关文法
这个M就是一个可空符号
根据刚才的算法
对这里面 产生式里面
M只要含有可空符号的
我们都把它一个产生式变成两个产生式
就是M出现或不出现
然后再把这个ε产生式去掉
那这个文法实际上就变成为这个产生式
这个文法就不含ε产生式了
跟原来的文法 你看
它们除了相差一个ε这个语言
其他的都是等价的
这是化简之后的这个文法
下面我们再看前面给的
那个下推自动机转上下无关文法的时候
那里面有19个变量
24个产生式
我们消除了它的无用符号之后
我们得到的只有这么简单的文法
这个文法里面
就发现这里面 它有可空符号
有ε产生式
那根据刚才的方法
我们就消除它的ε产生式
那就得到这样的文法
这个文法是首先消除有用符号
再消除ε产生式得到的
这个文法是不是不含无用的呢
这个我们在之后再讨论
好 这节内容介绍到这里
谢谢大家
-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
-习题--作业
-期中考试
