当前课程知识点:软件理论基础 > 第十一章 上下文无关语言的性质 > 11.6 CFL的判定性质 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍上下文无关语言性质的第六节
上下文无关语言的判定性质
在判定性质里,首先
是空语言的问题
给了一个上下无关文法
如何判定这个文法的语言是空的?
这是给定的上下无关文法
要判定这个文法的语言是空的
只需要检查这个上下无关文法
它的开始变量
如果这开始变量是无用符号
这个语言肯定是空的
再看第二个问题
无限语言
给了一个上下文无关文法
它的语言是不是无限的?
给定的上下无关文法
按前面的方法,消除ε产生式
消除单一产生式
消除无用符号
然后构造它的依赖图
如果这依赖图里
从开始变量到终态有环
这个语言是无限的
看一个例子
给了一个上下无关文法
类似于
正则语言与正则文法的构造
得到的依赖图
它表示的语言
从初态到终态是有环的
为什么无限呢?
通过这个文法
得到从开始变量的推导
经过若干次推导,得到这个语言
这个语言中
i 是任意的
因此,它是无限的
下面再看
语言元素的归属问题
给了一个上下无关文法
如何判定一个串是不是属于这个文法的语言?
文法给出的语法分析树
通过解析算法搜索语法分析树
是穷尽的搜索
对于一个给定的文法
总是可以判定
但搜索的复杂度
是指数的
下面介绍另外一个方法
叫CYK解析方法
这个算法是由三个科学家
在上个世纪70年代,几乎同时发现的
算法是这样构造的
假设这上下无关文法
有一个Chomsky范式
通过Chomsky范式来分析
给定一个串
a1, a2, ..., an
看这个串是不是这个文法语言
的串
识别这个串
要构造这样的一些集合
是V中的一些变量
或者是非终结符构造的一些子集
子集 Xij 满足条件:
Xij 是V中的子集
如果变量 A 在文法中能够推出
ai、a(i+1)、一直到aj
A 就属于 Xij
介绍了变量的集合
包含什么样的一些变量
w
是不是文法语言中的串
只要判定S是不是属于X1n
如果开始变量属于x1n
从S就可以推出 a1a2...an
怎么计算 Xij?
用迭代方法
首先,如果 i=j
就是 Xii
Xii 包含哪些变量呢
它包含A 产生ai
这样的产生式的A都在Xii里
j 大于 i 时
看 Xij 里包含什么样的变量
这时候Chomsky范式
它的右边是两个变量
把这两个变量
分在两个集合里,就是存在一个k
把左边变量B,分在Xik里
右边变量C,分在 X(k+1)j 里
而 k 从大于等于i小于j里任意取值
实际上, 它遍历了这里所有的值
这样,就得到这个表示
这个图, Xij 是变量集合
它包含哪些呢?
Xii与X(i+1)j
Xi(i+1) 与 X(i+2)j
等等
一直到 Xi(j-1) 与 Xjj 作为一对
所有的变量构成的产生式
算法CYK它的复杂度
只是 n 的立方
比穷尽搜索方法少了很多
算法的思想有了
怎么去实现这个算法呢?
下面用填表法求Xij
以串a1a2a3a4a5为例
判定这个串
是不是文法语言的串
就看开始变量是不是属于X15
怎么计算X15?
根据刚才的计算方法
首先,看串a1
包含的变量A,产生a1
这集合是X11
A 产生a2 变量,是X22
产生a3的变量都在X33里
产生a4的都在X44里
产生a5的都在X55里面
可以给出来
接下来,考虑串a1a2
是哪些变量来产生的?
X12,分别由X11里的
变量放在左边
X22里的变量放在右边
得到这样的一个集合X12
同样
a2a3,是由X22里的变量
和X33的变量,得到 X23
按刚才的方法,得到X34
a4a5,根据刚才的方法就得到X45
之后
产生串a1a2a3
这样的变量,就是X13
X13根据刚才的做法
分别由X11和X23里的变量
X12和X33里的变量得到
这样,给出了X13
a2a3a4分别由这一对和这一对
得到 X24
a3a4a5分别由这一对和这一对
里的变量得到X35
再看a1a2a3a4
产生这串的变量就是X14
分别由X11、X24;X12、X34
这样的一些变量构成了X14
还有a2a3a4a5
这个串对应的变量
是由X22、X35;X23、X45;X24、X55
得到的变量,是X25
之后,看这个串
a1a2a3a4a5
产生这个串的变量就是X15
它分别由X11、X25;X12、X35;
X13、X45;X14、X55
得到了变量X15
最后,再看开始变量
在不在X15里?
如果在X15里
这个串就是这个文法
的语言中的串
否则就不是
刚才介绍了CYK算法
它是判定一个字符串
是不是属于这个文法的语言的
好像任何这样的问题都有算法实现
实际并不是这样
讲的这些语言中
实际上有很多是不可判定的
上下无关文法是不是歧义的?
上下文无关语言是不是固有歧义的?
两个上下文无关语言
它们的交是不是为空的?
两个上下文无关语言是不是相等的?
上下文无关语言是不是等于全语言?等等
这些问题都是不可判定的
在后面还要专门讨论
这节里介绍了
上下文无关语言的一些判定性质
特别介绍了CYK算法
CYK算法
可以将原来穷举算法的指数级
降低到n的立方
这个算法具有程序性
大家是学软件的
你们可以把这个算法
写成一个软件来做实现
当然,还有很多问题是不可判定的
前面介绍判定的,是给定的文法
那些问题不可判定的
是对任意的文法
和任意的上下文无关语言
这些都是没有算法
这节内容介绍到这里
谢谢大家
-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
-习题--作业
-期中考试