当前课程知识点:软件理论基础 >  第十章 下推自动机与CFG化简规范 >  10.7 CFG的化简与Chomsky范式 >  Video

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

Video在线视频

Video

下一节:Video

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

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

-习题--作业

第六章 正则语言的性质与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笔记与讨论

也许你还感兴趣的课程:

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