当前课程知识点：软件理论基础 > 第七章 上下文无关文法和推导 > 7.5 上下文无关语言 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍上下文无关文法和推导的第五节
上下文无关语言
我们前面已经讲过了
给了一个上下文无关文法
我们可以采用推导 规约
最左推导 最右推导
或者是语法分析树
得到一些句子
那这些句子就可以构成
这个上下无关文法的语言
但是这是自然语言表述
计算机它怎么样去接受
我们的一个上下无关文法的语言呢
这个语言的形式化定义是这样给的
给了一个上下无关文法
定义它的语言是用这个推导闭包来定义的
我们把这样的串
就是从开始变量在这个文法里面
经过若干次的推导
能够推导出终结符的串
把这些终结符的串放在一起
这就是这个文法的语言
这就是给了一个上下无关文法
你这样就得到它的语言
这是叫上下无关文法的语言
那如果是我没有文法
我们说一个语言叫上下无关语言
那是怎么定义呢
这个语言L它称为上下无关语言
那就是一定存在有一个上下无关文法
这个文法产生语言就是你给定这个语言
这叫上下无关语言
给了一个语言
你怎么去证明这个语言
是某个文法的语言呢
那一般来说
对于语言当中任何一个串
它必须要使用这个文法的
这个语言当中的串
反过来对于文法语言当中任何一个串
要证明这个串要使用这个语言
而对第一个证明
我们通常是对这个串的长度作归纳
而对第二个这个证明
我们通常是对这个文法的
推导的步数做归纳
我们下面看一个例子
这个例子是回文
这个回文 它就是使得这个句子
它是一个对称的
任何一个句子 它的翻转等于它自己
我们给了这个文法
这个文法它只有一个变量
它的终结符是0，1
当然开始变量还是S
产生式是由下面构成的
就是S可以产生0S0
S可以产生1S1
S可以产生0
S可以产生1
S还是可以产生空串
那这样的文法跟我们的回文
回文 我刚才讲了它是一个对称的
就是W跟W翻转
那这个文法产生的语言是不是这个语言
反过来这个语言是不是这个文法产生的语言
实际上我们就要证明两个方面
第一个方面
你要证明这个语言是这个回文的语言
实际上就对这个串
假如它是使用这个回文的话
你要对这个串的长度作归纳
就证明W是它的文法的语言
对第二个方面
假如一个串是这个文法的语言
你要证明这个串是使用回文
那就你对这个串在文法里面
它推导的步数作归纳
大家自己完成它的证明
当然我们这门课里面
更注重的是你怎么样去
同一个语言构造一个文法
还有通过文法怎么去推导出它的语言
这个是我们这门课当中的重点
最后要证明的话是大家
我觉得你们有兴趣
可以做这方面练习
在这章里面我们给出了
上下无关文法的定义
给出了从文法
怎么推导出句子的一些方法
包括规约 推导 最左推导
最右推导 语法分析树
以及它们之间的关系
我们最后介绍了上下文无关语言
好 这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
