Video在线视频

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

现在介绍下推自动机的第五节

下推自动机与上下无关文法的关系

在这一章开始

我们已经讲过

首先有上下文无关文法

我们希望能够找到一个自动机

跟这个上下文无关文法

它们之间是等价的关系

下面我们有这样的定理

上下文无关文法的语言

或者上下文无关的语言

它们都是一样的

我们放在这个集合里面

下推自动机它接受的语言

在这个集合里面

我们这个定理就告诉我们

这两个集合它们是相等的

那这就说明这个下推自动机

它接受的语言跟上下文无关文法

接受的语言完全是一致的

因为这是两个集合相等

它分两个方面

一方面是上下文无关语言

它应该包含在下推自动机这个语言里面

也就是说给了一个上下文无关文法

那一定存在一个下推自动机

它们两个语言是相等的

反过来这个集合包含在这个集合里面

那这是什么意思呢

给了一个下推自动机

一定能够找到一个上下文无关文法

它们两个语言是相等的

从这两个方面来看

它们都是能够存在或者找到

这里面就是涉及的一个构造

要证明这个结论

实际上就是怎么去构造

首先我们看给了一个上下文无关文法

我们怎么样去找下推自动机

那我们下面的构造是这样构造的

假设这个G给定一个上下文无关文法

那我现在要构造下推自动机

是空栈型的下推自动机PDA

你看前面有的同学就讲

我有了一个终态型的PDA不就足够了

为什么要介绍空栈型的PDA

现在那么就可以看到

我这里要找的PDA就是空栈型的PDA

这个PDA它只有一个状态

栈底符号是S

状态转移是这样定义的

首先 假如文法有这一类的产生式

就是A产生β这个产生式

这个状态转移里面A产生的β

都压到栈里面去

这个状态转移

实际上就是把产生式那个右边的

全部都压到栈里面去

还有另外一个状态转移是这样的

如果输入是A 栈顶是a

那我就把这个栈顶a弹出来

它整个状态转移就是分这两类

你看这非常简单

下面我们看个例子

我们给这个上下文无关文法

这个大家很清楚前面已经介绍过

那现在根据这个文法

我构造空栈型的PDA来构造

我根据刚才的做法状态我只写一个

输入字母我所有的终结符

都是我的输入字母

这个是我们的栈里面的符号

这个是栈底符号

那他的状态转移就这样给的

根据我们前面定义

如果我们的栈顶是变量E

我就把它所有的给的产生式右边的

全部压在栈里面去

如果栈顶是变量O

同样我把这个加压到栈里面去

把乘压在栈里面去

栈顶是v 我导入v就把这个v弹出来

还有如果导入d就把d弹出来

还有其他的这些都是栈顶

跟导入的符号是一样

都把它弹出来

这样就构造了一个空栈型的PDA

那这个PDA跟我们这个文法

它的语言是相同的吗

下面一个定理就告诉我们

假设你给的这个文法

经过之前在构造的空栈型的PDA

它们两个语言是相同的

要证明这个事实

实际上要双向证明

首先要证明如果串是文法的语言的话

那这个串输入这个下推自动机的语言

也就是我们这个箭头

我们假设这个串是文法语言的话

就一定从开始变量

经过若干次的最左推导

能够推导出W

这个归纳我们就用它的

这个推导的步数做归纳

这个开始变量就只一个

我们就不好在后面做归纳

那我们首先要证明

比这个结论更一般的结论

也就是任何一个变量A

经过若干步最左推导

能够推导出W

则这样一个即时描述

能够最终转移到这种即时描述

下面我们就对这个推导的步数做归纳

当n等于1的时候

那这个文法里面一定有这个产生式

我们用我们刚才构造的那个PDA

第二种状态转移函数的方法

实际上对这样的即时描述

我们就可以转移到它 就可以转移到它

那当n大于1的时候

n大于1的时候

那第一步我们假设它是使用的这个产生式

这个产生式那我们就可以

针对这个产生式里面

它产生的这个变量 M的变量

我们就将这个串W

分成M个子串

其中这个XK这个变量

它经过若干步最左推导能够推导出WK

这个推导的步数实际上

要比整个这个推导步数要少一步

那我们就可以用归纳假设

我们这是最初的即时描述

经过了在这个产生式

我们得到了是这个即时描述

这个即时描述XK

因为当K等于是X1

X1它可以最左推导

推导出W1

而且这个步数

它比原来的步数是少一步的话

一定有存在这样的即时描述的转移

这个转移刚好把X1跟W1它抵消了

也就是得到这个关系式

这就是用了我们归纳假设

那同样 这个X2最左推导能够推导出W2

而且步数也比总共步数少一步

根据假设X2跟W2这个即时描述

也可以把这里给抵消了

等等按这个下去

最后能够转移到这种即时描述是这样的

从最初即时描述

最后转移到最终的即时描述

就说明这个串W

就被我们这个下推自动机接受的

下面我们要证明那个箭头的另外一方面

另外一方面就是对任何一个串

如果是这个串

被这个下推自动机接受的话

要证明这个串

也能够被文法这个语言能够接受

那是不是在这个文法的语言里面

下面我们就要证明对任何一个串

就是这个即时描述

它经过若干次转移能够转移到它

则这个文法的开始变量

一定能够推导出W

就要证明这些事实

要证明它

我们需要对这个即时描述转移

它的转移步数做归纳

要做归纳开始变量肯定是不行的

我们就先证明这样一个结论

对任意的一个变量

A对这样一个即时描述

最终能够转移到这个里面来画

则这个A一定在文法里面推导出X

对这个即时描述的这个步数做归纳

当这个转移只一步转移的时候

那肯定就有X就等于空串了

而且这个A产生ε

应该是这个文法的产生式

所以这个A就可以推出X

所以这个结论是成立的

那当n是大于1的时候

我们第一步那个转移

就用了这样一个产生式

对这个产生式那我们就把它

对应的那一个串X

分解为m个这个子串

就跟它是对应的

其中Xi在这里面的转移

都转移到这种即时描述

实际上这个划分是按这一个示意图

这个变量对应终结符串

变量对应终结符串

变量对应终结符串

不管这个Xk

如果是它本身是终结符的话

这个一结论是很简单

如果它是变量都有这个能够推导出Xi

因为我们是用归纳假设这个推导的

只要是它能够产生它

它就可以推导它

那这样A经过了第一次产生式得到它

最后每一次这个推导

你看 最后就能够推导出X

这里证明了对于任何一个变量A来说

A在下推自动机里面

能够转移到最终的即时描述

这个A就一定能够推出这个串

那如果我们把这个A

特别取为这个开始变量S的时候

那实际上我们就得到这个结论

对任何一个串

这样一个即时描述

能够转移到最终即时描述

也就是说这个串输入下推自动机的语言

这个S就一定能够推出W

也就是说这个W一定是文法的语言

那这样我们就证明了我们整个定理

给了一个下推自动机

怎么样把它转化为一个上下文无关文法

我们的构造方法是这样的

你给一个下推自动机

我们依然是空栈接受的PDA

那构造上下文无关文法

首先这个文法的变量该怎么选取

这个变量我们这个文法的变量V

采用这种方法

假设p、q是下推自动机的状态

任何一个状态

X是它的栈符号

我们把这三个符号构成的一个轴

用一个符号

这个方法表示

这个表示让它记为一个变量一个符号

就是它写入我们文法当中的一个符号

这个符号只是含有我们原来的下推自动机

状态p的信息

栈符号X的信息 状态q的信息

你看这里面有多少个变量

大家可以通过排列组合可以把它算出来

这还不够

我们另外还加一个变量

这个变量S作为开始变量

这就是我们新的文法它所有的变量

那给了变量之后

下面我们对这个变量定义它的产生式

我们定义对开始变量S

S必须到这个变量有产生式

这个变量是什么样呢

第一个是开始状态

第二个是栈底符号

第三个是p是任意一个状态

按这三元构成的一个变量

这个变量里面有多少个

那就看你状态q当中有多少个状态

整个这个产生式就有多少个

这是这样的一类产生式

第二类产生式

就是对p1Xq我们定义它的产生式

产生式我们要分两种情况

第一种情况

假如状态p输入a

栈顶符号是X

我输入这个a刚好把x弹出去

到新的状态q的话

那么我对这个变量就是p1Xq

它到这个a有一个产生式

这个产生式目的就是输入a

把这个栈弹出来 得到这个产生式

另外的一类具有复杂性

因为我们状态转移有可能是输入a

栈顶X

它不是弹出来的 它是变成一个串

在这种情况下

我们怎么去定义它的这个状态转移呢

我们的状态转移

它就包含就是这个p是这个p

X是这里的X

另外一个状态pk

是整个这个q当中任何一个状态

这样构成一个变量

它产生的是啥呢

是a是这个输入符号

下面得到了这一串这些变量构成的串

第一个变量 这个q是这里的q

X1是这里的X1

p1是q中的任何一个状态

这样得到了第一个变量

你只要是p取定了

第二个变量里面的第一个状态

跟它是一致的

X2是这里的X2

p2又是任何一个状态

但是只要它取定了

后面一个变量

开始的一个状态跟它是一致的

一直到这里最后一个变量是这样的

pk减1这个状态

跟前面一个状态是一样的

Xk是这里的Xk

而这个pk不是其他的

跟这个pk是一致的

我们就得到了是这样的产生式

当然我们这里面说这个输入字母a

还可以是空串

这样给出来的这样的变量和乘式

大家就看好像是挺复杂的

实际上这个公式写的非常有程序化

我们要变成是实现的是很简单

下面我们看个例子

这个下推自动机

大家应该首先我们在前面介绍过

我们要通过这个PDA

这是一个空栈PDA

要构造它的上下文无关文法

它的状态有三个状态

它的栈符号有X和Z0两个栈符号

那按之前我们介绍构造它CFG的方法

首先我们看它的CFG的变量会有多少个

因为状态三个 栈符号是两个

那根据我们排列组合 我们就知道

应该是18个变量

再加上一个开始变量

应该是在文法当中这个V就是19个变量

你看变量就很多了

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

是一个比较复杂的

从变量就一下子就增多

这个变量给了之后

再看它的变量的这个产生式

首先就看开始变量

它就对应出三个产生式

首先我们在这个自动机里面

有这里有个状态转移

q0输入0

把栈底是Z0变为XZ0

那根据我们刚才介绍的产生式构成的方法

实际上就有这样的产生式

这个产生式里面qj

是q0、q1、q2当中任何一个状态

qi也是q0、q1、q2当中任何一个状态

这个产生式大家可以算一下

它有9个产生式

再看第二个这个状态转移

这里面输入0

把栈顶X变为AKX

那这样得到的这个产生式应该是这样的

这也是9个

我们再看这个状态转移

这个状态转移

它是输入1

把栈顶X 把它弹出来

那看我们刚才定义的

得到了这样一个变量到1的

它这个产生式

再看这样的一个状态转移

这个状态转移

它对应的这个产生式是这样的

还有最后这个状态转移

它对应的这个产生式是这样的

这样我们就按刚才的构造方法

把这个下推自动机

构造出跟它等价的上下文无关文法

那是否等价

那下面我们有个定理要保证的

这个定理是这样叙述的

给了这样一个下推自动机

那按照上面的方法构造出的

这个上下文无关文法

它们的语言是相等的

也就是说它们是等价的

要证明这一点

跟我们前面的证明是一样的

对任何一个串

这个串输入这个下推自动机的语言

当且仅当 它输入这个文法的语言

这样证明的话是用归纳法证明

这个证明可能要比上一个定理证明

还复杂一点

我们在这里就不讲了 书上有

大家回去自己看一看就可以了

CFG与PDA等价里面

我们是这样证明了

我们的证明方法

首先我们对这个空栈型的下推自动机

它跟终态型的下推自动机 它们是等价的

然后 我们又证明了

空栈型的下推自动机

跟上下文无关文法它们是等价的

上下文无关文法

跟所有的下推自动机

它们完全是等价的

在这章里面我们又介绍了一类

新的自动机

叫下推自动机

这个下推自动机跟我们上一章讲的文法

上下文无关文法

它们之间是等价的

我们通过这个构造

就发现了你给了一个下推自动机

可以构造上下文无关文法

反过来也成立

今天的内容我们就讲到这里

好 谢谢大家