带你速通 自动机理论、语言和计算导论

· · 个人记录

写在前面

一如既往的简洁笔记。

书是由机械工业出版社出版的《自动机理论、语言和计算导论》第 3 版，翻译自由 John E. Hopcroft、Rajeev Motwani、Jeffrey D. Ullman 合著的 Introduction to Automata Theory, Languages, and Computation。如果你在清华校内的话可以去书店买到一本影印版。

先来点简单定义。一个 字母表 \Sigma 是一个非空有限集合，其中的元素被称作 字符。\Sigma^* 是由 \Sigma 中任意有限长度的字符串构成的集合。特别地我们用 \varepsilon 表示一个长度为 0 的字符串。一个 \Sigma 上的 语言 L 是 \Sigma^* 的某个子集。例如，空集、只含 \varepsilon 的集合都是任意字母表上的语言。

有限自动机和正则表达式

有限自动机

一个 确定型有限自动机（DFA） 拥有若干有限数目的节点（也作状态）和若干节点之间的有向边（也作弧、转移）。每条边被赋予了一个字符，该字符表示为了走过这条边，字符串的当前位置必须是哪个字符。对每个节点来说，其所有出边中不允许出现两条边拥有相同的字符。自动机的某个节点被标记为初始状态，还有若干节点被标记为接受状态。称自动机接受某字符串当且仅当从初始状态开始，每次沿着和当前字符串首字符相同的出边行走并删去字符串的首字符，当字符串被删空时抵达某个接受状态。自动机接受的所有字符串的集合称为该自动机接受的语言。

非确定型有限自动机（NFA） 则是在上述定义中删去了 对每个节点来说，其所有出边中不允许出现两条边拥有相同的字符 这一限制。当有多条出边和字符串当前位置相同时，可以任意选择一条。只要最后有任意一种选择方案抵达某个接受状态，就认为 NFA 接受该字符串。

NFA 还有一种扩展，称为 \varepsilon-NFA。它允许某条边上没有字符，NFA 可以不消耗任何输入经过这条边。一般也称这样的边是 \varepsilon 边。

定理 DFA、NFA、\varepsilon-NFA 描述的语言类相同。

证明 先证每个 NFA 都和某个 DFA 等价。对于一个 n 节点的 NFA，我们用一个 2^n 节点的 DFA 来模拟其行为，其中每个 DFA 节点对应全体 NFA 节点的一个子集。

再证每个 \varepsilon-NFA 都和某个 NFA 等价。我们只需要让 NFA 中从 u 出发经过字符 a 所能到达的点的集合设置为在 \varepsilon-NFA 中，从 u 出发经过若干条 \varepsilon 边、一条 a 边能到达的点集，并且把 NFA 的接受状态设置成 \varepsilon-NFA 中经过若干 \varepsilon 边能抵达某接受状态的点集即可。\square

上面在 NFA 转 DFA 的时候状态数产生了指数级的上升。许多情况下可以通过剔除无用状态来化简这个自动机。然而，下面的定理表明，最坏情况下指数级的上升是不可避免的。

定理 令 \Sigma=\{\texttt{0},\texttt{1}\}。考虑由所有倒数第 n 个字符为 \texttt{1} 构成的语言。存在 n+1 节点的 NFA 接受该语言，但是任意接受该语言的 DFA 至少有 2^n 个节点。\square

该定理的证明并不复杂，利用抽屉原理即可。

正则表达式

在研究正则表达式之前，简要地定义语言上的三种运算。

正则表达式就是基于以上三种运算定义出来的。其定义基础是对每个 \Sigma 中的字符 a，用正则表达式 \textbf{a} 表示只含单个字符串 a 的语言（粗体只是为了方便区分正则表达式和字符）。还有表达式 \varepsilon 和 \varnothing 表示语言 \{\varepsilon\} 和空语言。接着，对于正则表达式 E,F，用 E+F、EF、E^* 分别表示在 E,F 对应语言上做上面三种运算的结果。

正则表达式和有穷自动机是完全不同的表达语言的方式，因而下面的定理看起来非常不可思议。

定理 正则表达式和 DFA、NFA、\varepsilon-NFA 描述的语言类相同。我们将其称为 正则语言。

证明 (i) 给定一个 DFA，考虑怎么用正则表达式模拟它。先假设 DFA 只有一个接受状态，有多个接受状态最后取并即可。我们考虑扩充 DFA 的定义：允许 DFA 的每条边上是一个正则表达式，DFA 接受的语言类是从初始状态到接受状态的路径上的正则表达式顺次拼接的并。

我们考虑一个个删掉除了初始状态和接受状态以外的点。假设要删去节点 s，s 到自身的自环上的表达式为 S；s 的入边分别来自 p_1,...,p_n，出边分别指向 q_1,...,q_m，上面的表达式分别为 P_1,...,P_n,Q_1,...,Q_m。不难验证，我们可以通过删掉 s，并在 p_i\to q_j 的边上写下

P_iS^*Q_j

来保持自动机功能不变。

如此操作，直到最后剩下两个或者一个点（需要考虑接受状态恰好是初始状态的情况）。最后一步是简单的。

(ii) 用 \varepsilon-NFA 模拟正则表达式是简单的。\square

正则语言的封闭性

定理 正则语言的取反、交、并、翻转都是正则语言。\square

定理 设 \Sigma_1,\Sigma_2 是两个字母表，f:\Sigma_1\to \Sigma_2^* 是前一个字母表到后一个字母表上字符串的映射，该映射自然扩充到映射 f':\Sigma_1^*\to \Sigma_2^*。则

(i) 若 L 是 \Sigma_1 正则语言，则 f'(L) 是 \Sigma_2 正则语言。（同态）

(ii) 若 L 是 \Sigma_2 正则语言，则 \{x\in \Sigma_1^*\mid f'(x)\in L\} 是 \Sigma_1 正则语言。（逆同态）\square

以上定理不难，交由读者证明。

否定一个语言是正则语言——泵引理

定理（泵引理） 对 n 节点 DFA，设 w 是长度 \geq n 的串，则可将 w 拆分为 w=xyz，使得

证明 设 p_i 是 DFA 读入了 w 长度为 i 的前缀后的状态，则由抽屉原理 p_0,...,p_n 必有两者相同，把这部分记为 y 即可。\square

泵引理是非常强大的工具。例如，可以用它直接证明：\{0^n1^n\mid n\in\mathbb{N}\} 不是正则语言。

最小 DFA

一个之前被遗漏掉的小科技，特地补上。

考虑我们怎么尽可能压缩一个给定的 DFA。我们执行以下操作：

  1. 删去所有不能从初始状态抵达的状态。
  2. 合并所有 等价的 状态。

这里，两个状态 p,q 是等价的当且仅当对任意字符串 w，从 p 出发经过字符串 w 后抵达的状态和从 q 出发经过字符串 w 后抵达的状态要么同时是接受状态，要么同时不是接受状态。容易发现这的确是一个等价关系。划分一个自动机的全部状态等价类有一个很巧妙的算法：

  1. 初始时我们只知道所有接受状态和非接受状态之间互不等价。
  2. 如果对字符 c 和状态 p,q，p,q 的 c 出边指向的状态已经被标记成不等价了，那么 p,q 也标记成不等价。
  3. 没有被标记成不等价的状态都是等价的。

正确性留待读者自证。时间复杂度是状态数平方乘上字符集大小的。

定理 以上算法能给出和原 DFA 描述相同语言的 DFA 中节点数最少的那一个，且节点数最少的 DFA 是同构的。

证明 考虑一台 DFA A 经过上述改造后得到了新 DFA M。我们要来证明：M 是和 A 识别相同语言的 DFA 中节点数最少的，且这些 DFA 若和 M 有相同的节点数则必然和 M 同构。为此，假设另一台 DFA B 和 A 等价，不妨对 B 也执行以上算法得到 DFA N。

首先来证明：M 中任意状态至少和 N 中一个状态等价。首先注意到 M 初始状态和 N 的初始状态是等价的，其次注意到若 M 中状态 p 和 N 中状态 q 等价，那么对任意字符 c，p 的 c - 后继和 q 的 c - 后继也必然等价。又由于 M 中每个状态都可以从初始状态走到，因此每个 M 中状态都和 N 中至少一个状态等价。

其次注意到任意两个 M 状态不可能同时和一个 N 状态等价，否则这两个 M 状态也等价，与上面的算法矛盾。于是 N 的节点数不可能小于 M。

最后如果 M,N 拥有相同的节点数，那么上面的等价关系事实上构成一个 M,N 状态间的一一对应，容易发现转移边也一定是相同的，故两个 DFA 同构。\square

下推自动机和上下文无关文法

上下文无关文法

我们先来举一个上下文无关文法的例子：

S\to \varepsilon S\to 0S1

在这里，A\to B 表示 “如果一个字符串可以被写成 B 的样子，那么它属于 A”。例如，上面第一行表示 “空串属于 S”，第二行表示 “如果 t 是 S 中的串，那么在 t 两边各加一个 0,1 也是 S 中的串”。容易发现 S 描述的语言就是 \{0^n1^n\mid n\in\mathbb{N}\}，所以上下文无关文法能描述一些正则表达式表达不了的东西。

我们稍微形式化一下以上的讨论。一个上下文无关文法（一般简称文法）需要一套符号表（上面的文法中只有 S）并指定其中一个代表整个文法（上面的文法的代表当然就是 S），一套终结字符表（也就是被描述的语言的字符集，在上面的文法中是 \{0,1\}），以及一套对应规则。

书上把判定一个字符串是否属于某个文法的过程搞得很复杂。考虑到本文读者应该都是 OI 选手，我们直接从 表达式树 的角度来定义：一个字符串属于某个文法当且仅当存在一棵有根树使得：

随之而来的一个问题是文法的 二义性。我们把二义性定义成：一个字符串可以被至少两棵不同构的表达式树接受。考虑以下定义在 \{1,+,\times,(,)\} 上的文法，它试图接受所有合法的算术表达式：

E\to 1 E\to E+E E\to E\times E E\to (E)

注意到它事实上以两棵截然不同的表达式树接受 1+1\times 1，一棵先算乘法，另一棵先算加法。这有时候是很致命的。幸运的是在这个例子中我们可以有办法回避二义性：像通常那样钦定乘法优先于加法，且钦定运算是左结合的。

自然要问：是否存在通用方法解决文法的二义性问题？以下两个结果是非常让人沮丧的。

定理 存在一个上下文无关语言，使得任意描述它的文法都是二义的。

定理 不存在图灵机能判定一个文法是否是二义的。

前一个定理的例子是 \{a^nb^mc^md^n\}\cup \{a^nb^nc^md^m\}，可以证明它不可避免地对 a^nb^nc^nd^n 类型的串生成两个表达式树。严格的证明课本上并没有给，似乎要读论文。后一个定理由于涉及到图灵机的定义，我们放在后面。

我们以一个有趣的小问题结束本节：

练习 构造一个上下文无关文法，接受全体 \{\texttt{a},\texttt{b}\}^* 中不能被写成 xx\ (x\in \{\texttt{a},\texttt{b}\}^*) 的形式的串。

下推自动机

下推自动机（简称 PDA）是对有限自动机的加强。一个下推自动机除了像有限自动机一样拥有有限个状态外，还有一个可以用来存储的无穷长度的栈，自动机可以根据栈顶的内容来做出不同的判断。

我们稍微展开说说。对于下推自动机的每一个状态和每一个栈顶符号和每一个输入字符，我们都可以设置应该转移到的状态以及应该对栈采取的操作。这里，对栈采取的操作只能是在弹出原栈顶后在栈顶插入一个新字符串。注意，和 NFA 类似，对于下推自动机的每一个状态和每一个栈顶符号和每一个输入字符，可以有不止一种转移策略；另外我们还允许 \varepsilon 转移，也就是不消耗输入字符串的转移。也就是说，PDA 被定义为具有不确定性。形式化地说，PDA 的转移是由一个函数 \delta:Q\times(\Sigma\cup\{\varepsilon\})\times T\to \mathcal{P}(Q\times \Sigma^*) 确定的，这里 Q 是状态集，\Sigma 是待输入语言的字符集，T 是允许的带符号集（要求其大小是有限的），\mathcal{P}(X) 表示集合 X 所有子集组成的集合（因为可能的决策不止一种）。

当然了，对于一个 PDA，我们还需要细化它最终怎么接受一个字符串。具体来说，我们需要指定一个起始状态 q_0\in Q，一个起始的栈的状态，以及终止时怎样是可以接受的。方便起见，我们一般认为有一个固定符号 Z_0\in T 称作 栈底标记，一般不会将这个符号弹出栈中，也不在栈的非底部使用这个符号；初始时栈中只有单个 Z_0 符号。终止时，我们可以圈定一个状态的子集 Q_F\subset Q，PDA 接受一个字符串当且仅当存在一个合法的操作序列使得处理完全部字符后 PDA 的状态在 Q_F 中，这种接受方式被称为 终态接受；也可以用一种比较特别的方式接受，规定 PDA 接受一个字符串当且仅当存在一个合法的操作序列使得处理完全部字符后 PDA 清空了自己栈上的全部字符（包括 Z_0），这种接受方式称为 空栈接受。一个简单的结论：

定理 空栈接受和终态接受的 PDA 表达能力等价。也就是说，对于一台空栈接受的 PDA，存在另一台终态接受的 PDA 使得二者接受相同的语言；反之亦然。

当然，我们也可以类似地定义 确定型的下推自动机（DPDA）。也就是说，对函数 \delta，我们要求 |\delta(q,s,t)|\leq 1，也就是每个转移集合只包含最多一种决策；同时如果某个 \delta(q,s,t)\neq \varnothing\ (s\neq \varepsilon)，那么 \delta(q,\varepsilon,t)=\varnothing。DPDA 也可以用终态接受或空栈接受，可以证明以下结论：

定理 空栈接受的 DPDA 不能同时接受两个有前缀关系的串；除此以外它与终态接受的 DPDA 能力相同。

在继续下去前，我们先来举几个例子。

例子 任意 DFA 可以直接看成是 DPDA，\varepsilon - NFA 可以直接看成是 PDA。这说明正则语言包含于能被 DPDA 终态接受的语言。

例子 DPDA B 处理仅包含左右小括号的字符串，其带符号只有两个 \{Z_0,X\}，每次读到左括号插入一个 X，读到右括号检查栈顶是不是 X 并弹出一个 X；其以终态接受且唯一的状态是接受状态。容易发现 B 接受所有合法括号串的前缀。注意到这并不是正则语言，也即上面的包含关系是严格的。

例子 DPDA P 接受的语言为 \{x\texttt{c}x^R\ |\ x\in\{\texttt{a},\texttt{b}\}^*\}，方法非常简单：直接将前半部分全部扔到栈上。PDA P' 则通过猜测哪里是全串的一半的方式接受 \{xx^R\ |\ x\in\{\texttt{a},\texttt{b}\}^*\}，也即全体长度是偶数的回文串。有结论：P' 接受的语言不能被任何 DPDA 接受，也即 DPDA 接受的语言严格包含于 PDA 接受的语言（注意和 DFA/NFA 的差别）。

下推自动机和上下文无关文法表达能力的等价性

本节的内容是构造性地证明以下重要定理：

定理 下推自动机和上下文无关文法表达能力是一致的。

我们将它们所能接受的语言合称为 上下文无关语言。

证明 显然我们分成两方面来证：

任意上下文无关文法可以被改造为一个下推自动机 我们考虑一个只有一个状态的空栈接受 PDA，它的带符号集合为文法中全体符号与全体输入字符。我们先在栈底标记上推入初始符号。对于文法中每条规则 A\to A_1\cdots A_k，我们定义一个 \varepsilon 转移：弹出栈顶的 A，依次推入 A_k,...,A_1；再对每个字符定义一个可以消去对应栈顶符号的转移。容易发现二者是等价的。

任意下推自动机可以被改造为一个上下文无关文法 设有终态接受的 PDA M，我们构造的上下文无关文法包含以下符号：

\{[pXq]\ |\ p,q\in Q,X\in T\}

其中，[pXq] 表示全部能让 PDA 从状态 p 走到状态 q，并恰好弹出栈顶符号 X 并且没有读取过 X 以下字符的字符串。对于 PDA 中的转移 (p,s,t)\to (q,t_1\cdots t_k)，我们在文法中添加规则

[pt_1q]\to s[pt_1r_1][r_1t_2r_2]\cdots[r_{k-1}t_kq]

（对所有的序列 r_1,...,r_{k-1}\ (r_i\in Q)）。容易说明两者的等价性。\square

上下文无关语言的性质

不管是从文法还是 PDA 的角度都很容易证明：

定理 上下文无关语言的并还是上下文无关语言。\square

定理 设 \Sigma_1,\Sigma_2 是两个字母表，f:\Sigma_1\to \Sigma_2^* 是前一个字母表到后一个字母表上字符串的映射，该映射自然扩充到映射 f':\Sigma_1^*\to \Sigma_2^*。则

(i) 若 L 是 \Sigma_1 上下文无关语言，则 f'(L) 是 \Sigma_2 上下文无关语言。（同态）

(ii) 若 L 是 \Sigma_2 上下文无关语言，则 \{x\in \Sigma_1^*\mid f'(x)\in L\} 是 \Sigma_1 上下文无关语言。（逆同态）\square

但是这里值得注意的是：上下文无关语言的取反不一定是上下文无关语言！考虑语言 \{xx\ |\ x\in\{\texttt{a},\texttt{b}\}^*\}，可以感性理解它并不是上下文无关语言。（如果有哪位读者会证这个请告诉我一声，谢谢！）但是在本章第一节的练习中我们确实证明了它的取反是一个上下文无关语言！进一步地，两个上下文无关语言的交不一定是上下文无关语言。

不过，我们还有下述定理：

定理 上下文无关语言和正则语言的交是上下文无关语言。\square

从 PDA 和 DFA 的角度出发证明比较简单。

上下文无关语言的泵引理

不会否定一个语言是上下文无关语言怎么办？多半是装的，学学泵引理就好了！

为了方便，我们先来讨论对任意上下文无关文法进行简化的手段。可以发现，任意一个文法都可以改造成只包含以下两种形式的语句的样子：

简单来说我们希望语法分析树是一棵完全二叉树。

……嗯？好像不对？注意到以上形式的文法不可能识别到空串。不过这是小问题，我们重新叙述一遍：任意不识别空串的文法都可以改造成上面的形式。

唔，似乎没有那么显然。我们还是大概讲一下流程：

  1. 对于 A\to B_1\cdots B_k 这种长语句，我们可以设置一堆辅助变量 C_1\to B_1B_2，C_2\to C_1B_3，……，然后 A\to C_{k-2}B_k。
  2. 处理空串。这里我们首先判定文法中每个符号 S 能否识别到空串，如果能那么建立一个新符号 S' 表示 S 除去空串的结果。然后对于 A\to BC，如果 B 能识别到空串那么把这条拆分成 A\to B'C 和 A\to C，以此类推，最终把所有能识别到空串的符号删掉。
  3. 处理 A\to B。这一步其实就很简单了，考虑把所有这样单个的转移关系建成一张有向图，然后求两两可达性，最后对 A\to BC，分别把 B,C 替换成各自可达的全体可能点即可。

在完成了以上改造后，我们终于可以来叙述泵引理了。

定理 对于任意上下文无关语言语言，存在正整数 n 使得对任意长度不小于 n 的字符串 z，都能把 z 打断为五部分 z=uvwxy，使得

证明 我们先找来任意一个描述该语言的文法，然后将其按以上手法改造。（如果该语言接受空串只需要强行删去即可。）设改造后文法中有 m 个符号，令 n=2^m。考虑 |z|\geq n 产生的一棵语法分析树，这棵树的树高至少为 m+1。拉出树上最深的节点到根的路径，取出最深的 m+1 个节点，由抽屉原理这些节点中至少有两个相同。接下来看图说话。

\square

拓展内容 我们有一个比泵引理更强的引理 奥格登引理：

定理 对于任意上下文无关语言语言，存在正整数 n 使得对任意长度不小于 n 的字符串 z 以及 z 中标出的任意 n 个位置（以下称为特殊位置），都能把 z 打断为五部分 z=uvwxy，使得

  3. \forall k\geq 0$，$uv^kwx^ky$ 在上下文无关语言中。$\square

（期末考试附加题，呜呜呜呜呜。）

证明的话简单来说就是考虑关键位置形成的虚树。好长，好难写，流泪。

图灵机

图灵机是什么

虽然我觉得大家肯定都知道图灵机是什么，但是为了严谨还是来写一写。

可以想象有一条无穷长的、向两边延伸的纸带，划分为若干格，每个格可以写入某个有限的符号集 T 中的任意符号。方便起见我们用全体整数为全体格子标号。一般我们认为 T 中有一个特殊符号 B\in T 称作 空格，除此之外还包含了全体输入字符。图灵机除了这条纸带外还有一个控制器，一开始这个控制器位于 0 处。此时，在 0,1,...,n-1 的位置写下了某个待判定的字符串，其他位置上的字符全是空格。控制器有一个有穷的状态集合 Q，控制器中内嵌了一个函数，这个函数根据当前控制器本身的状态和当前所处位置的带符号决定当下的行动，需要指出：

  1. 控制器进入哪个状态。
  2. 向纸带当前位置写入什么内容。
  3. 控制器向左还是向右移动。

此外，图灵机还可以在任意时刻宣布停机，接受 / 拒绝该字符串。

形式化地，图灵机可以用一个函数 \delta:Q\times T\to (Q\times T\times \{\texttt{left},\texttt{right}\})\cup\{\texttt{accept},\texttt{reject}\} 来描述。之所以如此大费周章，是因为我们需要从这种表示方法中得出一个结论：全体图灵机的等价类是可数的，也就是说，存在从自然数集到全体图灵机的满射。在下一节中，我们将利用这个映射来探索 图灵机不能做什么。

图灵机不能做什么

在继续下去之前，我们先进行一些澄清。对于一个特定的输入，一台图灵机可能有以下三种反应之一：（在有限步内）接受、（在有限步内）拒绝、死循环。如果一台图灵机从不死循环，则称它接受的语言是 递归语言；而对于一般的图灵机，它接受的语言被称作 递归可枚举语言。也就是说，一个语言是递归语言，当且仅当存在一台图灵机对于该语言内的字符串一定给出接受的结果，且对于非该语言内的字符串一定给出拒绝的结果，这时也称该图灵机是该语言的 判定算法；一个语言是递归可枚举语言，当且仅当存在一台图灵机对于该语言内的字符串给出接受的结果，且对于非该语言的字符串给出拒绝的结果或者死循环。

对于上一节中提到的满射 f，我们构造语言 L_d\subset \{\texttt{0},\texttt{1}\}^*：w\in L_d 当且仅当图灵机 f(w)（这里把 w 看成 w 所表示的二进制数）的图灵机 不接受 字符串 w。L_d 称为 对角化语言。我们有

定理 对角化语言不是递归可枚举语言。

证明 假设有图灵机 M 对于该语言内的字符串给出接受的结果，且对于非该语言的字符串给出拒绝的结果或者死循环。由于 f 是满射，存在 w 使得 f(w)=M。可以发现无论 M 接不接受 w 都会导致矛盾。\square

我们还需要一个简单的结论：

定理 递归语言的补是递归语言，从而非递归语言的补是非递归语言。\square

证明很简单，将接受 / 拒绝反转即可。

我们再构造一种语言 L_u，这种语言包括所有的二元组 (w,M)，其中自动机 M 接受字符串 w。（严格来说在这个描述下 L_u 并不是语言，不过把 L_u 映射成字符串集合的手段很多，我们这里不探讨技术细节。）L_u 称为 通用语言。我们显然可以用一个图灵机来模拟另一个图灵机的操作，因而通用语言是递归可枚举语言。但是通用语言的补不是递归可枚举语言（否则可以证明对角化语言是递归可枚举的）。根据上面的定理可得

定理 通用语言是递归可枚举语言但不是递归语言。

事实上我们有以下的定理：

定理 设 \mathcal{L} 是任意由 \Sigma 上的语言构成的集合，且 \mathcal{L} 既不是空集也不是全集。则不存在判定 一台图灵机接受的语言是否在 \mathcal{L} 内 这一问题的算法。

另外还值得提到的是波斯顿字符串问题的不可判定性。波斯顿字符串问题是指：给定正整数 k 以及 2k 个字符串 x_1\sim x_k,y_1\sim y_k，判断是否存在非空整数序列 i_1,...,i_t 使得 x_{i_1}+\cdots+x_{i_t}=y_{i_1}+\cdots+y_{i_t}。这实际上也告诉我们：一个上下文无关文法是否有二义性是不可判定的。

图灵机能做什么

我们一般认为：图灵机和计算机的能力是等价的。也就是说，可以在图灵机上使用的编程技巧非常之多！

首先，最基本的是让图灵机拥有 有穷记忆。这实际上是通过在有穷状态中增开一维表示记忆完成的，实际上 DFA / PDA 的编程里面也有很多这种操作。

第二个技巧称之为 多带，也即用单道图灵机模拟有一个带头但有 k 条带的图灵机。这也是简单的：把带符号集合设置成 k 条带各自符号构成的全体 k 元组的集合即可。在此基础上进一步可以实现 多道，也即有 k 个带头的图灵机：让单带图灵机扫描所有非空格，并把扫到的当前各带头符号传进有穷记忆即可。

第三个技巧则是众所周知的 子程序。这个操作实际上非常简单。

和图灵机等价的一些装置

考虑 PDA 的一种特殊版本：可用堆栈符号只有一个。等价地说，我们只有一个整型变量，每次要么给它加一，要么减一，且只能获得它是否为 0 的信息。我们将这个计算装置称作 计数器。计数器的功能显然是 PDA 的子集。不过，我们有以下的神秘定理。

定理 有两个栈的计数器的功能和图灵机等价。

图灵机能模拟双栈计数器是很显然的，我们只证明双栈计数器能模拟图灵机。为此我们先证明

引理 三栈计数器能模拟图灵机。

证明 对图灵机 M，设它有 r 个带符号，将它的带符号用 {1,...,r} 编码，令 T=r+1。我们将当前带头位置右边（包括带头位置）的字符串按 T 进制编码，用第一个计数器维护它；左边的字符串同理，用第二个计数器维护它。那么我们每次需要对计数器 1/2 进行的操作有：乘 T、整除 T、对 T 取模，不难利用第三个计数器完成这一过程。\square

接着再证明

引理 双栈计数器能模拟三栈计数器。

证明 用双栈计数器的计数器 1 维护数值 2^i3^j5^k，其中 i,j,k 是三栈计数器的三个栈分别的值。另一个栈辅助进行加减乘除运算。\square