Video在线视频

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

下面我们介绍下推自动机的第四节

下推自动机的语言

我们前面讲过下推自动机和他的语言

我们把下推自动机

它接受的串放在一个集合里面

这个语言也叫做下推自动机的语言

但是 我们讲了这个概念或者这个定义

是一个自然语言

云交流是可以懂的

计算机是不懂的

况且我们之前介绍了下推自动机的时候

我们定义了有两类下推自动机

一个是终态型的PDA

另外一个是空栈型的PDA

那么它们这些语言又该怎么给呢

我们首先看终态型的PDA的语言

因为有了上一节定义了即时描述

也定义了传递闭包

有了这两个工具之后

我们再给下推自动机的语言

就顺理成章了

假设给了一个下推自动机

这个下推自动机是终态型的下推自动机

它的语言是这样定义的

这个集合是有这个即时描述

这个即时描述q是初始状态

串是给了这个下推自动机的字母

它构成的串

Z0是下推自动机的栈底符号

我们把这个即时描述

叫初始的即时描述

在这个下推自动机里面

经过若干次的这个转移

最后转移到这种即时描述

这个即时描述

把它称为最终的即时描述

这个即时描述有什么特点呢

剩余的串是空串

状态是终态

qf是终态

栈里面有什么我们不关心

只要是这个串构成了初始即时描述

经过若干次的转移

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

我们就把这样的串放在这个集合里面

这个集合就是叫做

这个下推自动机的它的语言

计算机它是懂你这个定义的

所以我们给出了终态型的PDA的语言

或者也叫PDA的语言

我们看个例子

这个自动机前面已经介绍过的

它接受的语言我们也知道

实际上我们看这个串

q0给的串就是Z0

这个即时描述就是初始即时描述

它经过若干次的转移

这个即时描述这是终态

输入 剩下输入是空串

这些是最终的即时描述

所以这个串就被这个自动机它接受的

那也就是这个串在这个自动机里面

一般来说对这样的输入串

构成的即时描述

都可以经过若干次转移

能够转移到这种即时描述

所以a的n次方 b的n次方

也在这个语言里面

也就是说这个自动机它的语言

也就是a的n次方 b的n次方

这是终态型PDA它的语言

也就是我们一般讲的PDA的语言

下面我们再介绍空栈型PDA

因为空栈型PDA它没有终态

那它的语言是怎么定义呢

下面我们再给了一个终态型的PDA

它的语言是用nm表示的

这个即时描述

这个即时描述是一个初始即时描述

在这个下推自动机里面

经过若干次的转移

最后转移到这个即时描述

这个即时描述

串 剩下的串是空串

栈里面是空栈

栈里面没有元素了

状态是什么状态 我们不关心

是任意的状态

这样的即时描述在这个自动机里面

我们把它叫做最终即时描述

初始即时描述在这个自动机里面

经过若干次的转移

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

我们把这个串放在这个集合里面

这个集合就叫做这个自动机的它的语言

也就是空栈型的PDA的语言

这个PDA有终态型PDA的语言

空栈型PDA的语言

这两种语言它们之间有什么关系呢

如果说它们都是不一样的话

那我们下面的讨论可麻烦了

下面我们就讨论

这两种下推自动机语言的关系

首先我们讨论的是空栈型的PDA

它可以转换到终态型的PDA

这个结论就告诉我们

对任何一个空栈型的PDA

一定存在一个终态型的PDA

它们的语言是相等的

或者说它们是等价的

那怎么证明这个结论呢

下面介绍它这个思路

给了一个空串型的PDA

这个pn他有若干个状态

q0是初态

接受串从初态开始经过转移

只要是栈清空了 串读完了

这个串就被接受

那我要构造一个终态型的PDA，PF

这里没终态

我就经过这个自动机去构造PF的时候

我就要加一个终态

从这个自动机到终态 你这个经过有转移

但大家想

要这个语言被新的那个PF接受的话

相当于这里面接受串之后

要到终态有个转移

但是在这个自动机里面

它怎么叫接受呢

是串都完了 栈清空了

串都完了 栈清空了

你说再到终态它能有转移吗

所以在这种情况下

是不能够到它有转移的

那我们为了克服这个问题

那么在前面增加一个初态

这个新的初态是p0

再增加这么一个转移

这个栈底符号里面我压一个Z0

这个Z0是PN它的栈底符号

我下面就到了PN这个自动机了

它的初态

在这个初态里面它就进行转移

我在对每一个状态

用x0在这个里面它没有

它是这个自动机的栈底符号

只要是栈底符号是x0

那我这个时候就到终态有个转移

你看 每一个状态我都增加这个转移

每一个状态增加这个转移

我们大家就可以看出被Pn接受的串

这个自动机里面一定是被接受的

反过来也是成立的

所以我们构造的这个终态型的PDA

只是在原来的空栈型的PDA里面

增加了两个状态

增加了一些状态转移

再增加了一个终态

这样得到的自动机

跟原来的空栈型的PDA

它的语言是相同的

下面我们再看终态型的PDA

到空栈型的PDA

给了一个终态型的PDA

我们有这样一个结论

一定存在一个空栈型的PDA

我用PN表示

它们两个语言是相同的

我们还是谈一个证明思路

我们是想通过这个终态型的PDA

是构造空串型的PDA

那给了这个是终态型的PDA

这个里面有初态还有些终态等等

那这里面串它接受是串都完了

之后落到终态 这个串就被接受了

那我们构造空栈型的PDA

那大家很容易想到

我只需要把这里面的终态

把它的这个栈情况

实际上这个串被它接受

也一定被新的自动机接受

所以我只需要这里对每一个终态

我增加这么一个转移

就是为了把栈清空

这里也增加了这个转移

为了就是把栈清空

但是这样得到的语言

跟原来的自动机它是一样吗

大家想想

好 到这里面它串都完了

它的栈要清空了才被接受

那是不是还有一种可能

就是在原来自动机里面它有串

它读完了 栈也清空了

但是它没有落到终态

那在原来自动机里面是不被接受的

那这样在新的自动机里

如果你把这个当做一个新的自动机的话

那它就被新的自动机就接受了

那这两个自动机就不等价了

为了解决这个问题

我们还是增加一个初态

在一个初态里面

在栈底 还是加一个Z0

这个Z0是PF这个自动机的

它的栈底符号

再到了这个PF里面来

转移到这个里面来之后

因为X0是新的自动机的栈底符号

它绝对不会在这个自动机里面

把X0弹出去

所以你就放心

我们再转移的时候

被它接受的串之后在新的自动机里面

一定是被接受的

反过来也是成立的

这样我们新的自动机 也是空栈型的PDA

在原来的自动机里面 我们增加了两个状态

再增加了这些状态转移

得到的自动机跟原来的自动机是等价的

这两种情形就说明我们两类PDA

一个是终态型的PDA

一个是空栈型的PDA

它们虽然定义了两个好像是不同语言

实际上它们这两个语言是等价的

这个等价也就是说

只要是终态型PDA接受的语言

我一定能够找到一个空栈型的PDA

它们的语言相同

反过来也是成立的

大家一定要注意

我们这里是在两类不同的

下推自动机里面是找它们是等价的

也可能出现有这样的情形

大家注意

就是我给了一个PDA

这个PDA它是带终态的

它可能有两种语言

一个是终态接受的

就是终态型的PDA的语言

另外还有一个是空栈型的

也就是串输入完了 栈清空了 这个语言

在一个自动机里面

有可能有两种语言

这两个语言

它一般来说是不同的

在两类自动机里面

它们一定是相同的

在这节里面我们介绍了

下推自动机的语言

好 这节内容介绍完毕

谢谢大家