前言
现在我们将会定义一个新的计算模型，堆栈机模型，并且注意：它的能力是与确定性图灵机模型等价的。本课程在这个时候介绍堆栈机模型主要有两方面的原因：
堆栈机用起来比图灵机更简单，至少在细节层面是这样的。
然而正式地为最基本的计算指定图灵机是很乏味的，且容易出错，同样的任务相对于堆栈机就比较轻松了。尽管两种模型是等价的，但是人们更愿意相信是图灵机抽象了普通计算机的能力。
堆栈机和图灵机的等价为我们提供了一个非常棒的例子来支持丘奇-图灵论题。
堆栈机模型是自然且直观的，特别是在本课程中相较于其他我们学习过的模型，你可以明确地想象构造一个 — 或者甚至你可以用纸来实现栈模仿一个。换言之，它就代表着机械过程。正如丘奇-图灵论题所预言的，你能使用这种模型来计算的任意事物也能使用确定性图灵机。
堆栈机模型类似于下推自动机模型，但不同的是堆栈机模型允许使用多个栈。光这一点就造成了天差地别。事实上，正如我们所知道的，仅使用两个栈就能堆栈机模型拥有通用的计算能力。还有一个不同点，我们只会考虑堆栈机的确定性变体（虽然我们能轻松定义一个非确定性堆栈机）。
知识点
堆栈机的定义
这个小节我们会正式定义确定性堆栈机模型，但是在进行定义之前，先提出一些特殊点会比较有帮助。
- 正如我们之前提过的，这个模型可能被看做PDA的确定性和多栈版本。我们也许会有任意数量$r$个栈，只要这个数量确定即可。对于任意正整数$r$，我们正式地定义$r$-确定性堆栈机。
- 简化一下，我们假设每个栈的栈字母表都是$\Delta$。这个字母表中必须包含一个栈底符号$\diamond$，也必须包含输入字母表$\Sigma$（它本身可能不包含符号$\diamond$）。我们要求输入字母表包含在栈字母表中是因为在计算开始时输入会被存储在栈1中（最左侧的符号在栈顶）。
- 堆栈机的状态集合$Q$必须包含一个初始状态$q_0$，还有停止状态$q_{acc}$和$q_{rej}$（这两个状态不能相等）。
- 堆栈机的每个非停止状态，$Q$中除了$q_{acc}$和$q_{rej}$的任意元素，总是与$r$个栈中的一个有关联，而且不是推入状态就是弹出状态。当堆栈机从从推入状态转变成其他状态时，和那个状态关联的栈总会推入一个符号，同样的当堆栈机从弹出状态转变成其他状态，和那个状态关联的栈总会弹出一个符号（假设栈是非空的）。
定义14.1. 一个$r$-确定性堆栈机（简称$r$-DSM）是一个7-元组
其中
1.$Q$是一个有限非空的状态集合，
2.$\Sigma$是一个输入字母表，也许不包含栈底符号$\diamond$，
3.$\Delta$是一个栈字母表，它满足$\Sigma\cup\{\diamond\}\subseteq\Delta$，
4.$\delta$是一个转移函数，形式为
并且
5.$q_0、q_{acc}、q_{rej}\in Q$分别是初始状态、接受状态和拒绝状态，它们满足$q_{acc}\neq q_{rej}$。
当我们提到一个DSM去没有说明$r$的数量时，我们只是想简单地表达某个确定数量的$r$-DSM。有时候我们并不在乎已知的DSM有多少个栈，所以就简单的当做这个数量未指定。
在转移函数的详细说明中，概念$Q^{\Delta}$指的是所有从$\Delta$映射到$Q$的函数集合。这个转移函数$\delta$的解释如下：
- 如果$p$是一个非停止状态，而且$\delta(p)\in\{1,…,r\}\times\Delta\times Q$，那么状态$p$是一个推入状态；如果有这样一个情况那么当机器处于状态$p$时，它将符号$a$推入栈$k$中，然后转移到状态$q$。
如果$p$是一个非停止状态，而且$\delta(p)\in\{1,…,r\}\times Q^{\Delta}$，那么状态$p$是一个弹出状态；如果有这样一个情况
其中$f:\Delta\rightarrow Q$，那么当机器处于状态$p$，它会将第$k$个栈的栈顶元素$a\in\Delta$弹出，然后转移到状态$f(a)$。注意这里有个条件分支：状态$f(a)$的机械转移取决于弹出的符号$a$。
如果这个情况下第$k$个栈是空的，机器就会转移到状态$q_{rej}$，对一个空栈执行弹出操作直接造成了机器拒绝。
堆栈机$M$对于字符串$x\in\Sigma^{*}$的计算从初始状态$q_0$开始，并且输入字符串$x\in\Sigma^{*}$存储在栈1中。具体一点，栈1的栈顶符号就是$x$的第一个符号，栈顶符号的下一个就是$x$第二个符号，以此类推。在栈1的栈底，也就是所有输入符号的下面，是栈底符号$\diamond$。所有其他的栈中最开始都只有一个栈底符号$\diamond$。
只要机器处于非停止状态，计算就会以自然的方式进行下去。如果到达了状态$q_{acc}$或者$q_{rej}$，计算根据情况则会停止。当然，和图灵机一样，也存在一种无限执行计算的可能，这种情况我们就说机器永远执行不会停止。
DSM的状态图
确定性堆栈机的状态图从某种程度来说和我们之前讨论过的模型类似，但是在某种程度上也有不同。通常，有向图中的节点表示状态，有向边（带有标签）表示转移，接受和拒绝状态也同样有标签。你能很轻松地根据一个特点认出DSM的状态图，节点是方形（带有圆角），不是圆形也不是椭圆。
在一个DSM的状态图中，节点本身，不是有向边代表着机器从一个状态转移时执行的栈操作（推入或者弹出）。每个推入状态必须有一个转移边指出，边上标有推入操作的符号，执行下一个状态。每个弹出状态对应每个可能的栈符号都有一个条转移边指出，指向计算转移的状态（取决于弹出的栈符号）。
我们通常会为栈取$\mathsf{X}、\mathsf{Y}$和$\mathsf{Z}$这样的名字，而不是叫他们栈1，栈2，栈3等等，因为这样代称更为自然，更接近于算法中的堆栈机描述，就像我们在计算机程序中使用的栈命名。
图14.1是一个3-DSM的状态图。在这个图中，栈1（计算开始时存着输入字符串）的名字是$\mathsf{X}$，另外两个栈的名字是$\mathsf{Y}$和$\mathsf{Z}$。这个DSM接受语言
的所有字符串，并且拒绝这个语言（基于字母表$\{0,1,\sharp\}$）的补集中的字符串。
按顺序来说还有两个关于DSM状态图的附加信息。第一，除了接受和拒绝状态意外，我们我们倾向于将每个独立状态的名字移出状态图。因为这些名字和机器的功能是无关的，忽略它们让状态度看起来不那么混乱。当然偶尔存在状态名称有用的时候，我们会将状态名称写在节点的上方或者下方。
第二，虽然每个确定性状态机都假定是有拒绝状态的，通常我们并不会表示在状态图中。当你观察一个弹出状态时，如果有些可能的站符号没有出现转移箭头，缺失的转移就是拒绝状态。
比如，在图14.1中，初始状态没有标注$\diamond$的箭头，所以隐藏的含义就是如果$\diamond$从$\mathsf{X}$中弹出，机器就会进入拒绝状态。
子程序
与我们常用的编程语言类似，我们可以为堆栈机定义子程序。这位堆栈机的描述提供了很大程度的简化。
比如，看看图14.2中的DSM的状态图。在我们讨论这个机器之前，我们知道如果说一个栈存储这个字符串$x$，我们的意思是栈底符号$\diamond$的位置在这个栈的底部，$x$的符号出现在这个占地符号之上，$x$最左侧的符号在栈顶。这种用辞我们不会使用在符号$\diamond$出现在$x$中的情况。使用这种用辞，图14.2的DSM的行为就是计算开始时如果$X$中存储了任意字符串$x\in\{0,1\}^{*}$，那么计算结果是接受，并且$X$的存储变成空串$\epsilon$。换句话说，这个DSM在擦除$X$中的字符串后停止。
这个DSM执行的简单处理在某些更为复杂的DSM可以最为很有用的子程序，当然需要做个小改动：可以选择任意栈来代替$\mathsf{X}$进行擦除。如图14.3，我们使用一个速记符号表示子程序。
更具体一点，图14.3的左侧是一个假想的DSM，虚线框部分自于图14.2。注意，我们没有将接受状态也加入虚线框，因为我们需要的不是接受而是在擦除完成后进入下一个状态。我们也没有将“pop $\mathsf{X}$”放在初始状态，因为我们的控制器会通过某个状态进入到这个状态。事实上，在假想的DSM中可能有多个转移能进入到“pop $\mathsf{X}$”状态。
图14.3的右侧我们将左侧虚线框波分使用标有“$\mathsf{X}\rightarrow\epsilon$”的矩形框来代替，这个矩形框看起来很像一个状态，我们也可以把它想象成一个状态，只不过附带一些更为复杂的弹出或者推入操作，然而实际上就是代表而左侧状态图的虚线框部分。
这种模式我们可以复用在任意DSM上。也就是，如果我们想把一个DSM做为子程序，我们总是可以这么做：
- 让原来DSM的初始状态变为某个转移点。
- 移除接受状态，原来指向接受状态的地方可以指向更大的DSM中的“其他状态”，只要子程序完成控制器就会决定这个“其他状态”的指向。
自然而然，在定义和使用子程序时一定要小心，因为如果子程序修改的栈在计算中也用于其他目的，那么计算就很有可能出现崩溃。当然这种事情也发生在计算机程序的子程序中。
还有一个例子如图14.4所示，这个堆栈机讲一个栈的内容复制到另外一个栈，并且使用了第三个栈作为辅助来完成这个任务。具体一点，假设栈$\mathsf{X}$存储了一个字符串$x\in\{0,1\}^{*}$，栈$\mathsf{Y}$和$\mathsf{Z}$存储空字符串，图中3-DSM接受时 — 栈$\mathsf{X}$和$\mathsf{Y}$都存储着字符串$x$，而$\mathsf{Z}$仍然存储这个空字符串。总的来说，如果$(\mathsf{X},\mathsf{Y},\mathsf{Z})$一开始存储着$(x,\epsilon,\epsilon)$，那么接受状态的$(\mathsf{X},\mathsf{Y},\mathsf{Z})$将会存储$(x,x,\epsilon)$。
如果我们希望在更复杂的DSM中使用这个DSM作为子程序，我们可以将整个DSM（去掉接受状态）表现在一个矩形框中，和我们图14.3所做的一样。加一个标签写上“$\mathsf{Y}\leftarrow\mathsf{X}$”。
再来一个DSM做为子程序的例子，图14.5。注意，在这个状态图中我们使用了前面提到的两个子程序来进行简化。在每个新的子程序被定义之后，我们自然会用它来描述新的DSM。图中这个DSM是讲一个翻转后存储在$\mathsf{X}$中。它使用了一个辅助栈$\mathsf{Y}$来完成这个任务 — 但事实上它还用到了一个辅助栈$\mathsf{Z}$，隐藏在子程序$\mathsf{Y}\leftarrow\mathsf{X}$中。总的来说，它将$(\mahtsf{X},\mathsf{Y},\mathsf{Z})$中的字符串由$(x,\epsilon,\epsilon)$变成了$(x^R,\epsilon,\epsilon)$。
顺便说一下，通常我们不会列出堆栈机中用到的辅助栈 — 这里我们这个做是为了了解他们的使用。只要辅助栈的使用是正确的，我们就可以忽略掉它。
DTM和DSM的等价
现在我们将要讨论确定性图灵机和确定性堆栈机是等价的计算模型。这要求我们从两个方面来进行讨论：
- 已知一个DTM $M$，存在一个DSM $K$来模拟$M$。
- 已知一个DSM $M$，存在一个DTM $K$来模拟$M$。
正如我们上一节课，我们不必一步对应一步来模拟：模拟器也许需要许多步骤才能模拟原机器的一个步骤。以上列出的两点的结论是，对于每个输入字符串$w$，$M$接受字符串$w$则$K$也接受，$M$拒绝字符串$w$则$K$也拒绝，如果$M$在$w$上永远执行则$K$也是。
这两种模拟我们分开进行描述。下面的描述不是正式的证明，但他们能提供足够的信息来说服你两种模型是等价的。
用DSM模拟DTM
首先我们将会讨论一个DSM如何模拟一个DTM。为了模拟一个已知的DTM $M$，我们将会定义一个DSM $K$，有两个栈，叫做$\mathsf{L}$和$\mathsf{R}$（分别对应“left”和“right”）。栈$mathsf{L}$将会存储$M$的磁头左侧的内容（顺序是反的，这样$\mathsf{L}$的栈顶元素正好是紧靠$M$磁头左侧的元素），而$\mathsf{R}$将会存储$M$磁头右侧的内容。$M$的磁头正在扫描的元素将会存储在$K$的内部状态中，所以这个符号不必存储在任意栈中。我们主要的任务就是定义$K$，是的$\mathsf{L}$和$\mathsf{R}$的推入和弹出操作可以模仿$M$的行为。
更明确一点，假设$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{acc},q_{rej})$是一个用来模拟的DTM。对于每个状态/符号对$(p,a)\in Q\times\Gamma$，DSM $K$都有一个状态集合。图14.6阐述了$p$是非停止状态的状态集合。如果$\delta(p,a)=(q,b,\leftarrow)$，图14.6左侧的状态和转移就模仿了$M$的这个动作：
- 将符号$b$写入$M$的磁带上，然后磁头向左移动，那么$K$则将符号$b$推入$\mathsf{R}$，目的是为了表示符号$b$在$M$磁头的右侧。
- 之前紧靠磁头左侧的符号现在变成了磁头正在扫描的符号，因为磁头左移了，那么$K$从$\mathsf{L}$中弹出一个符号，将它存储在有限状态控制器中。如果是$K$弹出栈底符号的情况，它会将栈底符号重新推入，然后在推入一个空格符号，然后重复这个步骤；插入多余空格符号的效果就和$M$移动到未访问的磁带区块一样。
- 当$K$弹出$\mathsf{L}$的栈顶元素后，它转移到了新状态$(q,c)$，符号$c$就是被弹出的任意符号。然后$K$继续模仿$M$的下一个步骤。
如果是$\delta(p,a)=q,b,\rightarrow)$的情况处理方式也是类似的，左右（栈$\mathsf{L}$和$\mathsf{R}$）交换即可。
对于每一对$(p,a)$，并且$p\in\{q_{acc},q_{rej}\}$，不需要模拟$M$的下一步，所以$K$根据情况转移到接受或者拒绝状态，如图14.7所示。注意，如果我们只关心$M$是接受还是拒绝，在停止的情况下对照磁带上的剩余部分，我们可以消除所有形为$(q_{acc},a)$和$(q_{rej},a)$的状态，并且将这些消除状态的转移直接指向$K$的接受或者拒绝状态。
$K$的初始状态是$(q_0,\sqcup)$，默认栈$\mathsf{R}$是栈1（它存储着输入和栈底符号），而$\mathsf{L}$是栈2。因此$K$的初始状态代表着$M$的初始状态，而且磁头正好扫描了一个空格符号，输入正好在空格所在区块的右边。
用DTM模拟DSM
现在我们来解释如何用一个DTM来模拟一个DSM。这个模拟背后的思路相当直接：DTM将会用它的磁带来存储被模拟的DSM的所有栈的内容，并且会效仿DSM在适当的时候更新信息。通常这将会需要很多步骤，因为DTM将会在磁带上来回扫描处理信息来模仿原DSM的栈。
更具体一点，假设$M=(Q,\Sigma,\Delta,\delta,q_0,q_{acc},q_{rej})$是一个$r$-DSM。我们将要定义的DTM $K$，用来模拟$M$，的字母表是一个笛卡尔积：
也就是，我们需要的$K$有一个多轨道磁带，就像上一节课讲到过的。我们假设$\sharp$是一个特殊符号，它不包含于$M$的栈符号表$\Delta$，而且空格符号$\sqcup$也不包含于$\Delta$。图14.8提供了一段描述说明这个磁带是如何模拟$k$个栈的。和前面一样，我们默认$K$真正算作空格符号的是$(\sqcup,…,\sqcup)$，$M$的输入字符串$a_1\cdots a_m\in\Sigma^{*}$，将会被定义为磁带符号字符串
符号$\sharp$的目的是为了在$K$的磁带上标记一个位置；$M$的栈中的内容总是在这些$\sharp$符号左边。$K$做的第一件事，在模拟$M$的步骤之前，是扫描（从左到右）找到输入字符串的末尾。在每个轨道的输入字符串后的第一个磁带区块上，放置了一个栈底符号$\diamond$，再往后一格放置$\sharp$符号。一旦放上了这些$\sharp$符号，他们会保留到模拟过程结束。然后DTM向左移动磁头，停留在$\sharp$符号上，开始模拟DSM $M$。
DTM $K$会将$M$的状态存储内存中，有一种理解方式是想象对于每个$M$的$q\in Q$，$K$都有一个对应的状态集合（这个和前一小节的证明类似，不同的是前面我们用的是状态/符号对，这里只是针对每个状态）。DTM $K$定义完成，再开始模拟之前它的初始状态被设置为$q_0$（也就是$M$的初始状态）。
对于每个$M$的非停止状态$q\in Q$有两种可能性：推入状态或者弹出状态。在任意一种情况下，都有一个索引为$k$的栈与这个状态关联。在这两种情况下，$K$的行为如下：
- 如果$q$是一个推入状态，那么一定存在一个符号$a\in\Gamma$被推入栈$k$。DTM $K$往左扫描直到在第$k$条轨道上找到一个空格符号，将这个空格符号重写为$a$，和$M$一样改变$K$的内存中的状态。
- 如果$q$是一个弹出状态，那么$K$需要知道栈$k$的顶部元素是什么。它往左扫描直到在第$k$条轨道上找到一个空格符号，再往右移动找到栈$k$的顶部元素，根据情况改变$K$的内部状态，将这个符号重写为空格。很自然，$M$会有对空栈进行弹出的操作，$K$也会发现这一点（因为在$\sharp$的左边没有了非空格符号），它马上就会转移到拒绝状态。
两种情况下，在推入或者弹出操作被模拟后，$K$都会将磁头向右移动找到$\sharp$，这样又可以进行$M$的下一步模拟。
除非$K$存储了$M$的一个停止状态，否则他会继续模拟$M$的步骤，最终他会根据情况接受或者拒绝。某些情况下模拟过后$K$在磁带上的内容会很重要，比如$M$是计算一个函数而不是简单地返回拒绝或者接受，当然有人会这么定义$K$，在接受或者拒绝之前它先从磁带上移除$\sharp$和$\diamond$符号。