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的立方

这个算法具有程序性

大家是学软件的

你们可以把这个算法

写成一个软件来做实现

当然，还有很多问题是不可判定的

前面介绍判定的，是给定的文法

那些问题不可判定的

是对任意的文法

和任意的上下文无关语言

这些都是没有算法

这节内容介绍到这里

谢谢大家