当前课程知识点:软件理论基础 >  第十章 下推自动机与CFG化简规范 >  10.6 消除单一产生式 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

Video

下一节:Video

返回《软件理论基础》慕课在线视频列表

Video课程教案、知识点、字幕

欢迎同学们来到《软件理论基础》的MOOC课堂

现在介绍上下无关文法的化简与规范的第三节

消除单一产生式

什么是单一产生式呢

单一产生式它是形如A产生B

A和B都是变量

这类产生式我们就称为单一产生式

我们看单一产生式

它只会增加了变量个数

所以我们消除单一产生式

是减少文法的变量

而且简化文法的推导

这利于文法的规范

那怎么样去消除单一产生式

我们首先计算一个叫单一偶对

单一偶对是指这样的

给了一个上下无关文法

这个里面A在文法里面经过若干次推导

能够推导出B

而且这个推导过程当中

只使用了单一产生式

你看这样的A和B就叫单一偶对

消除单一产生式就计算单一偶对

单一偶对怎么去计算

就用归纳方法

给了一个上下无关文法

首先 对任何一个变量A

A跟A 它自己跟自己我们叫一个单一偶对

接下来如果A和B是一个单一偶对

而B产生C是一个单一产生式

那我们就说这个A和C

也是一个单一偶对

这也是一个归纳的推导法

通过这个算法

就可以给出G的所有单一偶对

而且恰好给出来了

一方面得到了所有的偶对

一定是单一偶对

而且任何一个单一偶对

都可以通过这个算法得到

计算了单一偶对之后

接下来我们就可以消除这个文法的

单一产生式

我们下面通过这个步骤来消除

给了一个上下无关文法

首先计算G当中的所有的单一偶对

把它的单一偶对找出来

下面对这样的一个单一偶对AB

假如B在这个文法里面

有产生α这样一个产生式

那这个B产生α不是单一偶对

那我们就把这个α

作为A产生α这个产生式填进去

那这种方法我们就可以把所有的

这样的单一偶对做这个替换

再然后再把这个G当中的

所有单一产生式 把它去掉

这个时候这个文法跟开始文法里面

它是等价的

而且它是不含有单一产生式

这就是我们得到的定理

这个定理 这个文法 跟原来的文法是等价的

这个证明大家可以看看书上面

书上面都有

下面我们看个例子

这是我们之前给出来的

下推自动机转上下无关文法

经过首先消除无用符号

接下来我们消除ε产生式

得到的文法是这样的

这个文法里面

实际上这就是一个单一产生式

根据前面的方法

要消除这个文法里面的单一产生式

那消除的方法

首先要归纳计算它的单一偶对

计算单一偶对 这里面

有A是A 是一个单一偶对

A这个变量它可以产生0BD

这是一个非单一产生式

A还可以产生0B

这也是一个非单一产生式

那把这个就替换到前面的这个M里面去

或者增加新的产生式

我们就得到这样的S产生0BD

S产生0B

还有其他的关系式

再把原来单一产生式去掉之后

这个文法跟原来的文法是等价的

它不含有单一产生式

整个得到这个文法大家回顾一下

下推自动机转上下无关文法

那个转化我们有很多个变量

很多个产生式

经过消除无用符号

再消除ε产生式

再消除单一产生式得到这个文法

这个文法大家再仔细看看

发现了经过这个步骤

发现它里面还会有一些有用的符号

为什么产生有用的符号呢

这个我们在下节里面再做说明

好 这节内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

-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

-习题--作业

第六章 正则语言的性质与DFA优化

-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

-习题--作业

第八章 CFG的应用与文法的二义性

-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

-习题--作业

第十章 下推自动机与CFG化简规范

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。