Video在线视频

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

现在介绍确定下推自动机的

终态型DPDA与空栈型DPDA

介绍PDA的时候

我们曾经也介绍过

终态型PDA和空栈型PDA

我们证明了这两类下推自动机

它们实际上是等价的

也就是接受的语言都是相同的

它们都是上下无关语言

现在介绍了DPDA

这两类确定下推自动机

它们是什么关系呢

首先 我们介绍一个叫前缀性质

什么是前缀性质呢

假如一个语言它具有这样的一个性质

就是它在这个语言当中

不存在两个串

x和y

其中一个串是另外一个串的前缀

我们就说这个语言它是具有前缀性质的

你看 这里面条件是很强的

在这个语言当中它不存在这样的串x、y

这x、y是任意的

只要它们不相等就可以了

它一个串不是另外一个串的前缀

这个条件它怎么讲呢

下面我们看这个语言

这个语言它的输入字母只有一个a

这是一个正则表示

由这个正则表示生成的语言

当然是正则语言

这个语言大家可以检验

它就不满足这个前缀性质

所以连正则语言

它不一定满足这个前缀性质

所以前缀性质它的要求是非常强的

那我们介绍这个前缀性质是干什么用的

下面我们再看看这个

终态型DPDA与空栈型DPDA之间的关系

我们有这个定理

这个语言L是空栈型的DPDA的话

它一定满足下面两个条件

第一个条件是这个语言

它一定要具有前缀性质

第二个是这个语言

一定是某个终态型的DPDA的语言

它是空栈型的DPDA

一定满足这两个条件

反过来满足这两个条件

它一定是空栈型的DPDA

这个定理的证明我们书上有

大家可以在底下去看一看

这个证明我们把它作为一个练习

我们在这个定理里面

这两个条件说明空栈型的这个DPDA

它的语言一定是终态型DPDA的语言

但是我们刚才已经给出一个例子

说明里面正则语言它不一定满足

这个前缀性质

那这说明什么

这个空栈型DPDA

它包含在终态型这个DPDA里面

它这个包含是一个真包含

这就是我们终态型DPDA与空栈型DPDA

它们之间不等价的

这跟我们之前讲的PDA就不一样了

下面我们再看看这个语言L是WCWR

因为中间有一个字符C

我们就可以构造一个DPDA来解释这个语言

而且这个语言它是具有前缀性质的

所以这个语言

它就是一个空栈型的DPDA的语言

下面我们再看另外一个例子

这个语言0的*闭包

它是不具有前缀性质的

但是它是一个正则语言

那就说这个语言

它不是一个空栈型的DPDA的语言

这两个例子它说明什么呢

在第一个例子里面

就说明了空栈型的这个DPDA语言

它不一定是正则语言

因为这个语言我们可以用泵引理来证明

它不是正则语言的

空栈型的DPDA语言不一定是正则语言

而第二个例子说明是正则语言

它不一定是空栈型的DPDA的语言

综合这两个例子我们就说明了

空栈型的DPDA语言

它与正则语言之间它是没有关系的

在前面我们介绍DPDA语言

也是终态型DPDA这个语言

它与正则语言它们是有关系的

但是空栈型的DPDA语言与正则语言

它是没关系的

下面我们再看看DPDA语言

与二义文法之间的关系

我们有这个定理

如果L它是一个空栈型DPDA语言

这个语言它一定存在一个无二义的文法

就是上下无关文法 来接受这个语言

上下无关语言它有的文法接受这个语言

它是没有二义的

但是有的文法接受这个语言

它是具有二义的

还有这样的语言

只要是接受这个语言的话

这个文法是一定具有二义的

这叫固有二义

那一般的说我们对固有二义语言

去构造它的文法 那肯定是不行

我们要排除这个语言

那啥样的语言是

不是固有二义

我们现在看这个空栈型DPDA语言

它不是固有二义的

这个定理的证明 我们可以用前面讨论的内容

证明了那个PDA

就是下推自动机与上下无关文法

之间的关系的时候

曾经是讲了从PDA去构造上下无关文法

这个构造当时是用空栈型的PDA来构造的

我们把那个构造方法移到这儿来

我们用DPDA的 就是空栈型的DPDA

我们来构造跟它等价的上下无关文法

这个构造得到之后

可以证明对任何一个字符串

那这样得到的上下无关文法

它只有唯一的一个最左推导

那就说明我们得到的这个文法

的确是无二义的上下无关文法

所以空栈型的DPDA的语言

一定是非固有二义的

那这是空栈型DPDA

对于终态型DPDA有什么性质呢

下面我们有这个定理

如果L是一个终态型的DPDA

它也有一个无二义的文法

那这个定理也说明终态型DPDA这个语言

也是非固有二义的

这个证明我们可以这样

我们假设有一个新的一个符号

假设是个$吧

它不出现在这个语言当中

根据这个语言L构造一个新的一个语言

这个语言就是在原来的L当中

任何一个串 后面加这样一个$

这就得到了这个L一撇这个语言

实际上都是L当中的语言的串

后面再加一个$

它每一个串里面都有唯一的一个$

因此这个语言它是有前缀性质的

所以根据前面的一个定理

它就有一个无二义的文法

来接受L一撇这个语言

我们假设这个文法就是G撇

它是无二义的

它接受这个语言

增加这样一个产生式

$产生空串

其他的都按G撇这个文法来构造

就得到了文法G

这个G实际上它产生的语言

就是我们原来终态型的DPDA的语言

这样我们就证明了终态型的DPDA

也是一个非固有二义的语言

我们再看看DPDA的语言

与非固有二义之间语言它之间

到底是什么的关系

我们看看这个语言

它是一个非DPDA的语言

但是这个语言有一个非常简单的

无二义的文法来产生这个语言

这个语言它可以用这样的一个CFG来产生

从这个例子我们可以看出来

这是一个非固有二义的一个语言

但是它也不是DPDA的语言

那这样就说明存在一个非固有二义的

上下无关语言

它不是任何DPDA的语言

把DPDA的语言放在几个集合里面

把非固有的二义的上下无关语言

放在集合里面

这个语言它是包含着这个里面

但是这个包含它一定是真包含的

在前面我们介绍了DPDA的语言

其他语言之间的一些关系

我们前面在讲上下无关文法的时候

我们讲给了一个语言

怎么去构造一个文法

不是一个简单的问题

现在给了一个语言 上下无关语言

怎么构造一个下推自动机

也是很困难的问题

那下面在这方面

我们再介绍几个构造方面的例子

首先介绍这个语言

输入字母是abc

它的字符串是

a的i次方b的j次方c的k次方

I等于j

或者是j等于k

对这个语言我们要设计一个PDA来接受它

要构造的话

i等于j

k是任意的话

这个串是被接受的

或者是j等于k

a是任意的 也可以被接受

那根据这个特点

我们设计这自动机 给个初态

这个里面我们abc都不输入的话

当然也满足这个条件

然后跳到q1

q1这个地方它就是输入字母a

输入任何的字母a

只有a的时候 没有b和c

说明这个b和c都等于0

那当然这个是被接受的

接下来 我们再把a跟b来匹配

原来是输入一个a

我这个自动机的压一个a

我要跟a匹配我就输一个b

我就弹出一个a

就到状态q2

在状态q2的时候

它就一定执行输入一个b我就弹出一个a

直到后来我这个b都输入完了

而且跟a是匹配的

说明我到了栈底符号z0

这个时候这是c

我就到q3

这个时候就被接受

对任意的都是被接受的

那这个时候如果是我没有a和b

那这个它也是被接受的

这个地方我们也可以再加一个转移

这里是空串z0 它也是被接受的

这是对前面的a的个数和b的个数

相等的时候

b的个数和c的个数相等

那我们怎么比较呢

从这儿来

a是任意的

接下来我输入b

输入一个b我就压一个b进去

到q4

q4始终是输入b压一个b

输入一个b压一个b

b跟c来比较匹配

然后又c输入一个c就弹出一个b

到q5这个让它

q5始终是输入b弹出c

到最后

如果是栈底符号

或者是我们原来的a

这个就到了接受状态

这个语言得到这个PDA就接受了这个语言

只用这七个状态就可以了

下面我们再看另外一个例子

我们设计一个PDA

接受这样的语言

a的数量是b的数量的两倍

如果a的数量是b的数量是相等的话

我们在前面已经设计过这样的PDA

我们只需要两个状态就可以了

现在是a的数量是b的数量的两倍

我记得我讲上下无关文法的时候

设计过接受这个语言上下无关文法

那个文法设计的并不是太难

那现在我设计一个下推自动机

这个设计我们该怎么设计

要用前面设计a的个数跟b的个数相等

那种思想就可以了

我们假设初态是q1

因为a的数量是b的数量的两倍

那我首先输入a的时候

我就压个0

如果是栈顶是0的话我就压个0

但如果栈顶是1

1是哪来的 我等会儿讲

我就弹出一个1

这个我在q1这个状态就OK了

那下面输b的时候

输b如果栈顶是z0

那我们加两个1

如果输b栈顶是一个1

我还是压两个1

也就是说只要是栈顶是z0或者1

我都是压两个1

那如果是栈顶是0的时候怎么办呢

我下面就转到q3来

弹出一个0到q3

这个弹出一个0

因为我要求的是a的个数是b的个数的两倍

那再下来

我弹出一个0还不够

接下来我这里

如果栈顶是1或者是栈底符号的时候

都是做这样的变换

再发现一个栈顶是0的时候

我就回到这个里面来

我就不需要输入 就到这里来

直到后来我的输入串用完了

栈顶z0的时候

这个时候就被接受了

我们可以证明这个下推自动机

它接受的语言就是这个语言

这个下推自动机还可以做一些简化

你比如说在这一块转移

用这种简单的两个状态转移就可以了

这个自动机接受的语言也是它

所以我们说一个语言

可能有多个下推自动机来接受它

我们在设计的时候

可以采用一个比较好的方法

这里就希望我们多练习了

下面我们再看看另外一个例子

a的数量是b的数量的三倍

刚才是a的个数是b的个数的两倍

那现在a的个数是b的个数的三倍

实际上我们有了刚才a的个数

是b的个数两倍的设计思想的时候

我们再设计这个语言的PDA实际上并不难

那我们就用刚才类似方法输入a的时候

栈底符号是z0或者是0 我压一个0

如果栈顶是1的时候输入a 弹出个1

输b栈顶是z0或者1 我压三个1

那如果是输b

栈顶是0的时候

我就弹出个0到q3

到q3要执行的就是下面这个动作了

实际上跟我们前面a的个数

跟b的个数是两倍

实际上很类似的

我们可以证明这个PDA接受的语言

就是这个下推自动机

从这几个例子大家可以看出

从一个语言构造一个PDA是有很多技巧的

这些技巧我们只有通过多练习来逐步掌握它

因为我们要是构造软件

软件是做什么

实际上是对一个具体的工程需求

你要设计程序

工程需求是什么

工程需求实际上是语言

那对这个语言我怎么去构造程序

或者我设计满足这个语言的这一套结构

这个结构设计实际上就是

你的文法或者你的下推自动机

这节内容介绍完毕

谢谢大家