Video在线视频

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

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

下推自动机的定义

在上一节里面我们给出了

下推自动机的大致的描述

从我们的介绍里面给出的新例子里面看

下推自动机它有状态

它有输入字母

它有栈符号还有初始状态

栈底符号等等

我们可以把这些特点

跟我们之前讲的DFA、NFA它们对应起来

这就是我们下推自动机的形式化定义

下推自动机可以描述成为一个七元组

这个七元组里面有有限个状态构成的集合

输入字母构成的集合 栈符号构成的集合

在状态转移函数 初始状态 栈底符号

还有一个终态

我们说是一个集合

在这里面初始状态

是状态集当中的一个状态

栈底符号是栈符号当中的一个符号

而F是状态集当中的一个子集

在这里我们强调了很重要的就是

状态转移函数

状态转移函数它是有状态集

输入字母 还有栈符号

这边是一个三元组 到这里是一个幂集合

我们这表示的是г*

实际上就是有栈符号的

所有的有限个符号构成的集合

而我们这里讲了是终态型的PDA

另外还有一种下推自动机

是叫空栈型的下推自动机

在这个定义里面

其他的跟我们的都是一样的

只是它没有终态

这样我们下推自动机实际上

有两种这个形式化定义

在这里面我们要做说明

我们说下推自动机 下推自动机

实际上就是我们讲的

非确定的下推自动机

这是默认的

第二个有时候我们说这是个PDA

我们刚才不是讲了PDA有两种定义

一般的我们就指的这个终态型的PDA

如果我们要讲这个PDA是一个

空栈型的PDA

那我们要特别强调这是一个空栈型的PDA

如果没有做这种强调

我们讲这个PDA

那认为它就是一个终态型的PDA

在我们下推自动机里面

刚才给出的模型是一个七元组

七元组里面描述实际上最重要的

是状态转移函数

我们只要把状态转移函数给出来

实际上这个下推自动机也给出来了

那状态转移函数

它也可以用一个状态转移图来表示

下面我们看个例子

这里给出了是四个状态

构成了一个状态转移图

下面我们看对这个输入

在这个下推自动机里面

它是怎么样运作的

输入串是aaabbb

首先 这个下推自动机是处于在初始状态

我们没有做任何操作的时候

栈里面它有一个栈底符号Z0

在第一次这个状态转移的时候

是没有多任何符号

再也不发生变化

直接就跳到状态q1

你看再也没有发生任何变化

接下来在q1这个状态输入a

这里面是栈上面是压了一个符号a

你看栈里面上面压了一个符号a

还是到状态q1

再输入一个a

我们这个状态转移

还是用这个栈里面压一个符号

还是在状态q1

再读入一个a的时候

我们发现了跟刚才一样

栈里面压一个符号

还是在q1这个状态

在导入b的时候

导入b我们看

导入b 它就用这个状态转移了

把栈顶a就弹一个a出来了

把这个a弹出来了

就转移到q2这个状态

再输入一个b的时候

就是用这个状态转移

栈里面再弹出一个a

还是在q2这个状态

再输入一个b的时候

栈里面如果有a

还弹出一个a

如果没有a 那当然就停止了

你看这有个a 又弹出来了

只要这里这个输入符号都输入完了

输入完了最后是栈底符号Z0

那Z0不变最后到q3

q3是终态

按之前讲的DFA或者NFA

那这里就串输入完了

最后落到终态 那应该是接受

那PDA的接受 它怎么定义呢

一个串 输入串 被下推自动机接受

它应该满足所有的字符串（07：14）

而且最后落在

这个下推自动机的一个终态

特别说明的是

这个串被PDA接受或者不接受

跟栈里面是没有关系的

你栈里面我们刚才当然是栈顶符号

你可以不是栈顶符号

只要是落到终态就可以了

我们把所有PDA

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

就构成了这个PDA的语言了

这跟我们之前讲的DFA、NFA它的语言

实际上是很类似的

而对刚才的例子这个串

它就是被这个下推自动机接受的

一般来说这个下推自动机

应该接受串a的n次方 b的n次方

那我们把所有这些串放在一起

实际上这个语言就是a的n次方 b的n次方

这个语言大家应该熟悉

在之前我们讲正则语言的时候

这个语言它不是正则语言

我们用泵引理证明过

用DFA、NFA都描述不了的

但是用现在的下推自动机

就可以解释这个语言

这说明下推自动机

比我们之前讲的有些自动机

NFA或者DFA 达到的能力 它是不一样的

下面我们再看一个例子

这里有三个状态构成的下推自动机

输入字母是ab

那这个自动机

它接受语言应该是什么样的呢

我们看它这是输入a压入a

输入b压入b

输入a弹出a

输入b弹出b

可能大家一时从这个自动机

还看不到它接受什么的串

实际上这个自动机

它接受的语言是这样的一个特殊语言

是w，w反转

实际上是一个对称的一个串

被它接受

是不是这样

我们看一个具体的一个串

abba这个串

开始我们还是在初始状态

栈里面是栈底符号Z0

导入a的时候

我栈里面我导入一个a

栈里面就压一个a

还是在q0这个状态

再导入一个b

使用这个状态转移

栈里面就压一个b

实际上我每次在做的时候

这里有一个从q0到q1 一个ε跳转

它每次要么在这里做 要么跳这里来

它每次有两种选择

因为我们这是非确定的

也就是说我们现在每次都是猜

是不是到了这个串的中间了

如果到了这个串的中间 我就跳到q1

跳到q1 导入的是b

导入了b 栈顶是b

就弹出这个b

有同学说我栈顶如果是a怎么办

那你没这个转移的话就自动停机了

在导入a的时候

输入a的时候

栈顶是a 我弹出a

这个串输入完了

这个栈顶是Z0

Z0不变到q2

这个串那我们刚才定义就应该接受的

下面再看另外一个串

这个串是abbb

那同样我们按刚才的做法

开始处在开始状态

导入a的时候压一个a

导入b的时候 栈里面压一个b

实际上我的每一次操作的时候

它都有两种性质

那我猜是不是到了串的中间

到了串的中间

导入一个b 栈顶是b

我就弹出来了一个b

再导入b的时候 发现栈顶就不是b了

这个时候就没有转移了

这个时候就停机

就是按这种选择路径 它是执行不了的

那也许你刚才这种非确定这种选择

是不正确的

那我再换另外一种选择

这里导入a的时候 我栈里面压一个a

导入b的时候 栈里面压一个b

再导入b的时候 栈里面再压一个b

再导入b的时候

因为我都是在q0这个状态

栈里面还压一个b

这个时候我这个串读完了

串是读完了

但是要么是在q0这个状态

要么在q1这个状态 这不是终态

它也没有办法能够转到终态q2

所以采用什么样的路径

它都无法到达终态

那这个时候在这个自动机

没有路径来接受这个串

那也就是这个串被这个PDA是拒绝的

那一个串被一个PDA拒绝

我们是什么意思呢

我们就讲一个串被一个PDA拒绝

那就是不被它接受

要么这个字符串是没被读完

或者要么这个字符串实际上读完了

但最后没有落在一个终态

有那句话

这个字符串 它接不接受

我们都是与栈里面的元素是无关的

前面我们讲几个下推自动机例子

是给了下推自动机

我们看它解释串是什么

最后把它的语言找出来

那下面我们讨论

这个问题的另外一方面

就是我们给了一个语言

把它的下推自动机设计出来了

这跟我们之前讲的DFA或者NFA

是很类似的

因为这个问题较前面那个问题

它更有挑战性

下面我们看这个例子

给的语言是a的n次方 b的m次方

刚才我们给的例子是a的n次方

b的n次方

也就是m等于n的时候

下推自动机画出来了

现在是n大于等于m

那我们怎么样去把

这个语言的下推自动机设计出来

那设计这个下推自动机

就必须要把它的状态让它表示出来

首先我们给出初态是q0

这里表示你输入若干个a

然后再输入若干个b

只要是a的个数比b的个数多或者相等

这个串就被接受

你把a输入的时候记录下来

然后跟b来比较就可以了

那我就可以采用这种方法

导入a栈里面就压a

我就记录看有多少个a

当然这个时候我们用b的时候

它也满足这个条件了

所以这个串你在导入a的时候

它都是被接受的

然后在导入到b的时候

栈里面必须要有a

你看我栈顶是a

去掉一个a

就到另外一个状态q1

那这个时候说明你是有a

那a的个数肯定就不比b的个数少

所以就被接受的

然后我再输入b的时候

只要栈里面有a我就把a弹出来

还是在状态q1

这个自动机就是用两个状态

就描述了这个语言

当然我们严格说

是要证明这个自动机接受的串

在这个语言里面

反过来这个语言的串被这个自动机的表示

我们在这门课里面一般来说

我们只强调我们的设计

这个设计是正确的

也就是说你设计这个自动机

的确是接受这个语言的

我们就认为算正确的

有兴趣的同学你们可以证明

一个自动机是不是这个语言的自动机

或者语言是不是这个自动机的语言

严格说是要有这个过程的

下面我们再看另外一个语言

这跟我们刚才讲的语言又有一点差异

这是a的m减1次方 b的m次方

也就是说a的个数比b的个数少一个

如果是相等我们已经有了

如果大于或等于b的个数

那我们也有了

现在就说a的个数比b的个数少一个

我们设计这个自动机

设计这个自动机时候

我们还是想到之前讲的例子

这里不就是a的个数

比b的个数少一个吗

那即便少一个

我开始在这个初始状态里面

我的栈里面我进行这个操作

你少一个a

我原来是导入一个a 栈里面压一个a

再导一个a 栈里面压一个a

再跟b进行比较

那既然它少一个a的时候

我不妨就在栈里面首先压一个a进去

你看原来栈顶方式这里面

我压一个a进去

压一个a进去之后

在q1这个地方我再导入a我就压a

再导入a就压a

这时候按之前的设计实际上很类似

但是注意我这个时候a

导入的a我之前我压了一个a

b跟a比较的时候

只要是它相等了我就好办了

所以我导入b我就弹一个a

再导入b弹一个a

只要是这个串动完了

是栈底符号

那刚好就说明我这时候b比a

要多一个

这个时候就接受了

我们再看个例子

这个语言现在是a的n次方

b的m次方

我们刚才讲的一个例子是

n大于等于m

这个设计我们给出来了

只用两个状态就可以了

下面我们说这里是

n大于等于m减1

这个比刚才又要复杂一些

那我们就把之前我们讲过的几个例子

把它综合起来

实际上这个语言可以分解为

两个语言的并

一个是a的m减1次方 b的m次方

还有一个是a的m加k次方 b的m次方

也就是a的个数大于或等于b的个数

我们可以用这样的语言

把它这个语言表示出来

而这个自动机和这个自动机

我们都画过的

所以我们就用刚才的形式

把这个自动机表示出来就可以了

表示这个自动机

我们只需要栈里面压一个a就可以了

所以我们采用了方法

就把刚才的几个例子综合起来

就得到这样一个PDA

用三个状态表示的

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

下面我们再看一个稍稍复杂一点的例子

这里输入字母是ab，na（w）

就表示这个串当中a的个数

这个是表示这个串当中b的个数

而这个语言是表示这个串当中

a的个数跟b的个数相等的

都在这个语言里面

这个语言的自动机该怎么设计

之前我们曾经讲过一个例子

a的n次方 b的n次方

他们的确是a的个数跟b的个数相等

但是那个时候

我们看到的是它的次序前面一定是a

后面一定是b

而这里面串里面a的个数

跟b的个数相等

但是它们是没有次序的

它们是任意的排序

那在这样的下推自动机怎么设计呢

实际上这个设计这个下推自动机

并不复杂

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

首先在开始状态我们假设是k1

我们给出这样的状态转移

输入a栈里面我们压一个0

如果是栈里面是Z0的话

我们就变成0Z0

如果栈顶是0的话就变成00

那如果是输入a

栈顶是1

我们就弹出一个1

这里表示是栈符号跟输入符号

它可以相同也可以不同

栈的符号是0或者是1

而我们输入符号是a和b

栈顶符号你可以任意来设计都是可以的

只要是输入a的时候我们采用这种转移

那输入b的时候

栈顶是Z0我就压一个1

是1的话我就变成1

如果栈顶我输入b是0的话

我就弹出一个0

也就是a和b来进行匹配

如果这里面这个串输入完了

栈顶就是Z0不变就到终态q2

这样一个简单的自动机

我们说就可以接受这个语言

那是不是能够接受这个语言呢

我们下面从这个串里面看看

给出串是abbbaa

栈底符号是0

初始状态是q1

导入a的时候

这个状态转移 这是当前是Z0

Z0就变成了0Z0

再导入b的时候

因为栈顶是0就把0就弹出了

还是到q1

再到b的时候

刚才是栈底符号变成栈顶符号Z0

那我的Z0上面压一个1

就是Z0变成1Z0

再导入b的时候

输入一个b的时候

就是因为我们栈顶是1

把1变成1

再输入a的时候 发现栈顶是1

弹出一个1

再输入a的时候栈顶是1

也弹出一个1

这个串输入完了

我们栈顶就是Z0

Z0不变被它接受

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

刚才我们介绍了下推自动机的定义

和下推自动机怎么样设计它

从刚才几个例子里面

大家可以总结对下推自动机的设计

好 这节内容介绍完毕

谢谢大家