【原题】Finite Automata and Their Decision Problems
【译题】有限自动机及其判定问题
【作者】Michael O. Robin ，D scott
摘要：这篇文章中把有限状态机（Finite automata）当作对有限磁带的分类设备来考虑。每个一磁带自动机定义了一个磁带集（Each onetape automaton defines a set of tapes），一个两磁带自动机定义了一对集，诸如此类。将研究被定义的集之结构。介绍了一自动机的各种一般概念，而且它们到经典自动机的关系被决定了。一些关注自动机的判定问题显示可通过有效算法来解决；其它则显示为通过算法不可解决。
介绍（Introduction）
图灵机被广泛的认为是数字计算机的抽象原型；在这个领域内的工人却感到一台图灵机的概念对作为一个之于实际计算机的精确模型来说过于通用。众所周知，即便是对简单的运算（calculations），不可能在“图灵机为了任何给定计算所需的”磁带量上给出一个先验上界（a priori upper bound）。正是这个特性显示出图灵的概念不实际。
在最近几年，一台有限自动机的观念见诸文献之中。有那些“可用于存储和计算的（can be used for memory and computation）”内部状态数仅是有限的的机器（These are machines having only a finite number of internal states）。有限性约束表现出对一台物理计算机给出一个更好的近似法（The restriction of finiteness appears to give a better approximation to the idea of a physical machine）。当然，这样的机器不能像图灵机做的那么多，但是其（译注：指图灵机）优势“可以计算给定的任何一般递归函数”是可疑的，因为实际应用中非常少有这些函数。
已经发表的有关有限状态观念有许多相等形式 。这些中的头一个是McCulloch 和 Pith 3 定义的“神经网络（nerve-nets）”。神经网络理论已经被诸作者太多的提及了。我们特别受到影响，然而 通过 S. C. Kleene2的工作，其证明了一个重要的定理，刻画了这种设备的可能性（用Kleene的术语来说是“规则事件regular event ”概念）。J. R. Myhill，在一些未开发工作中，对 Kleene的结果给出了新的对待，而这是对该报告所专注的而言之实际起点。我们虽然没有采纳 Myhill所使用的指导图作为观察自动机的方法，但自始自终保留了一个机器式的形式体系（a machine-like formalism）允许和图灵机直接的比较。一个定义自动机的整齐格式 被 Burks and Wangl 以及 E. F. Moore4 而且我们的观点较之和形式化神经网络而言，和他们更接近。然而，我们已经通过去除一复杂的输出函数并让我们的机器简单的给出“是”或“否”的答案，采用了一种更简单形式的定义 。Myhill也是这样使用的， 但是我们对“非确定性（nondeterministic）”，“双向（two-way）” ，“多磁带（many-tape）”的机器之一般化看上去是新的。
在节1到6中，给出了一磁带，单向自动机的定义，而且其定理完全成熟。这些机器被认为是“黑盒子（black boxes）”仅有一个有限数量的内部状态，且以一种确定的风格回应它们的环境。
我们讨论的核心围绕在将自动机的应用当作，通过对独立磁带给出“是”或“否”的答案，之于磁带集起决定作用的设备（We center our discussions around the application of automata as devices for defining sets of tapes by giving “yes” or “no” answers to individual tapes fed into them）。对每个自动机而言，有可由该自动机“接受的（accepted）”相应的那些磁带集（the set of those tapes ）；这样的磁带将被作为可定义集来指涉。这些磁带集的结构，以及我们可在这些集上施行的各异操作，以及自动机和定义集之间的关系是这篇文献的广泛主题。
在对基础概念定义以及解释后，我们给出了，其继续工作由 Nerode5 ，Myhill，Shepherdson7 作出，一个直觉上对可定义集的数学刻画（an intrinsic mathematical characterization of definable sets）。这种刻画的结果成为一个有用的工具，既能证明“通过一个自动机可对特定的集合作定义（certain sets are definable by an automaton ）” 又可证明特定的其它集不可以。
在节4中，我们讨论到关系了自动机的判定问题。我们对是否一自动机会接受任何磁带考虑了三个判定问题（consider the three problems of deciding whether an automaton accepts any tapes），无论其对不同磁带是否接受一有限数字，也无论两个自动机接受完全一样的磁带。所有三个问题显示出通过有效的算法可以解决。
在第二章，我们考虑把一台自动机的概念一般化的可能性。一台非确定性（nondeterministic ）自动机，在其操作的每个阶段，有数个可能的行为选择。 这种广泛性（versatility ）使得我们能仅使用少量的内部状态去构建一个非常有力的自动机。然而非确定性自动机成为一种等价于普通自动机的机器（Nondeterministic automata, however, turn out to be equivalent to the usual automata.）。这个事实被用来快速的显示可以通过自动机去定义某些集合（certain sets are definable by automata）。
使用非确定自动机，自动机直接产出的一个预先给出的构造（ a previously given construction of the direct product of automata ）（定义7），以及对可定义集的数学刻画（the mathematical characterization of definable sets），我们对各种众所周知的“可定义集分类下的闭合属性（closure properties of the class of definable sets）”给出简短证明（例如，形成布尔代数的可定义集）。进一步的我们为了完整性包含了 Kleene关于规则事件定理之一个形式化（a formulation of Kleene’s theorem about regular events）。
为试图定义“接近图灵机观念的”自动机，当保留了“仅使用一个预先分配量的磁带（using only a preassigned amount of tape）”重要特性时，另一个一般化显示了其自身。我们放松了“自动机总是在一个方向上移动”条件，使得自动机可以来回移动。以这种方式我们获得了一个双向自动机的观念。在节7中， 我们考察了比较单向自动机和双向自动机的问题，“考察了有限自动机内存的本性（an investigation into the nature of memory of finite automata）”可以作为一个研究。一台单向机器可以被想象为仅有一个“表示字母系统的符号”键盘，和有来自通过连续敲打键来的输入磁带的序列（having the sequence from the tape fed in by successively punching the keys）。因此操作该机器就不需要永久的磁带记录（Thus no permanent record of the tape is required for the operation of the machine）。一台双向自动机，另一方面，不需要一个永久的，其可以在之上来回运行的实际磁带去尽力计算一个答案。足够惊讶的是，结果就是虽然有向后参考（backwards reference）的能力，双向自动机不比单向自动机更有力（two-way automata are no more powerful than one-way automata）。在机器内存的术语中，这意味着相关于一次计算的相关于“一台自动机可以通过向后参考去收集”的所有信息 ，总是可以通过“在一单向机器内的一有限内存（a finite memory in a one-way machine）”被把控。
在第三章我们研究了多磁带机器。这些自动机可以读取在多个不同磁带上的符号，我们采用约定俗成，即一台机器会在一磁带上读一会儿，然后变更控制并读取另一台机器，诸如此类（a machine will read for a while on one tape, then change control and read on another tape, and so on ）。因此，随一台双向机器，磁带对的一个集合就被定义了，或者我们可以说磁带之间的二进制关系被定义了（a binary relation between tapes is defined）。再次使用“非确定性自动机（nondeterministic automata）”这个有力的工具，我们就在两磁带自动机和单磁带自动机之间建立起了一种联系（we establish a relationship between two-tape automata and one-tape automata）。就是说，一个关系的域和范围通过“双磁带自动机是可由单磁带自动机可定义的磁带集（a two-tape automaton are sets of tapes definable by one-tape automata）”被定义了。来自以下的事实，不似单磁带自动机可定义的诸集合（unlike the sets definable by one-tape automata） ，是通过双磁带自动机定义的关系是不能形成一个布尔代数的（the relations definable by two-tape automata do not form a Boolean algebra）。“是否一个双磁带自动机会接受磁带对（whether a two-tape automaton accepts any pair of tapes），以及磁带对是否会接受一无限的数字对（ whether it accepts an infinite number of pairs）”的问题，显示是可以通过有效算法来解决的（shown to be solvable by effective algorithms）。
我们用简单的讨论“双向双磁带自动机（two-way, two tape automata）”来总结。这里即便是“究竟是否有一台自动机能接受任何磁带（whether an automaton accepts any tapes at all）”问题 通过一个有效的算法也是不可解决的。进一步的，双向自动机到单向自动机的规约是不可能的。总而言之，在单磁带自动机的属性和双磁带自动机的属性之间有明显的差异。对双磁带自动机属性的研究远远没有结束（The study of the latter is yet far from completion）。
第一章 单磁带单向自动机（ One-tape, one-way automata）
1.直觉模型和基础定义（The intuitive model and basic definitions)
一自动机被视作是一个黑盒子，可以对之问问题并从中得到一个“是”或“否”的答案。可以被问的问题数量将是有限的，为了简化，一个问题被解释为任何“任一来自提前给出的一个有穷字母系统的有限符号序列（arbitrary finite sequence of symbols from a finite alphabet given in advance）”。一种简单的“想象该自动机问问题的行为”方法就是把黑盒子想做是打字机键盘上有独立的符号。然后机器就被发动了，问题也打入了（Then the machine is turned on and the question is typed in）；在“问题结束”按钮按下之前，一道光显示一个“是”或“否”答案。关于“自动机如何可能物理的去表现（how the automaton could appear physically）”另外一个好的想象是使用“穿孔卡（punched cards）”。假设我们只是打了一个符号，或对到符号的卡片而言的代码数字（punch just one symbol or code number for a symbol to a card）；然后问题就简单是卡片的一堆栈了（a question is simply a stack of cards）。该自动机通过“以通常方式让堆栈一次读取一张卡片（having the stack read in a card at a time in the usual way）”被问了一个问题 。
为了本文的目的， 我们不会使用上述的任何图像，而是思考“在一维磁带上给出的（as given on one-dimensional tapes）”问题。该机器将被赋予一个读取头，其一次可以读取一平方的磁带（比如说，一个符号），然后这个读取头可以在磁带上前进一个单元，并正确的读取下一个平方。我们假设这个机器会在用完磁带的时候停下来。对一自动机的外部刻画就这么多了。
一自动机的内部工作不会分析的太深入。我们不是关心这个机器要怎么造出来，而是关心这个机器可以做什么（We are not concerned with how the machine is built but with what it can do）。内部状态的定义必需足够的通用以覆盖所有可以想象的机器，但是不需要涉及到自身带有电路的问题（with problems of circuitry）。不带不必要细节的获取通用性的简单方法是使用“内部状态概念（the concept of internal states）”。无论机器包含多少电线或者多少电子管或者继电器，其操作是由“该机器在离散时间间隔内的稳定状态（stable states of the machine at discrete time intervals）”决定的。一台实际存在的机器可能有十亿计的这种内部状态，但是从理论观点看数量并不重要 ，唯一的事实就是它是有限的。
作为一个进一步简化的设备，我们无需考虑该机器通过的所有中间状态，而唯一要考虑的是“直接进一步读取一个符号（directly preceding the reading of a symbol）”。就是说，该机器首先是读取一个符号或者磁带上的一个平方，然后才该机器可能在其准备好读取下一个符号前通过多个状态。为能够模仿自动机的行为，我们无需记住所有这些中间状态，唯一要记住的是“在状态机读取下一平方之前的最后一个状态（but only the last one it goes into before it reads the next square）”。实际上，如果我们制出了一张“从一个状态一个符号到一个新符号的所有转换（all the transitions from a state and a symbol to a new state）”表，然后该机器的整个的行为本质上就可以刻画了。
最后，为了从机器中得到答案，我们只需在“达到问题的终点时，‘是’光亮了的那些状态和‘否’ 光亮了的那些状态”之间作出区分 。再一次，为了简化， 人们认为所有的状态都是一个或者另一个范畴，但不可能同时属于多个范畴（it is assumed that all states are in one category or the other but not in both）。因此当相应于‘是’答案的制定状态的一类被给出时， 整个机器就被定义了 。现在留下来的就是对这些观念给出精确的数学形式。
首先给出一个有穷字母系统 ∑，在接下来的讨论中会得到确定。在该字母系统中的实际符号数并不重要。唯一重要的是所有被考察的自动机使用相同的字母系统（all the automata considered use the same alphabet ），从而不同的机器之间可以进行比较。为了说明，我们应当常常把 ∑ 想做是仅包含了字符 0 和 1。通过一磁带，我们应该理解来自∑的字符之任意有穷序列。我们也包含了空的没有符号的带子，标记为 Λ 。所有带子的类型标记为 T 。如果 x 和 y 是 T 当中的带子 ，然后 xy 标记通过“拼接 x 和 y（ splicing x and y together）”，或通过“并列（juxtaposing ）”，或通过“连接这两个序列（concatenating the two sequences）”获得的带子。
换言之，如果
x = σ0σ1 . . . σn-1
而且
y = τ0τ1 . . . τn-1
那么
xy = σ0σ1 . . . σn-1 τ0τ1 . . . τn-1
其中 σ 和 τ 都属于有穷字母系统 ∑。
我们观察到明显的两条定律
Λ x = x Λ = x
和
x（yz）= （xy）z
xyz 都是属于 带子类型 T 。
用数学术语来说， T 和并列操作（together with the operation of juxtaposition）一起形成了“由有穷字母系统 ∑产生的”自由半群（带单元 with unit）（free semigroup）。
我们应该常常有把磁带切成一片片的机会。比如，让
x = σ0σ1 . . . σn-1 ;
σ就是在 ∑中，且 n 指示了磁带 x 的长度。我们采纳了以下概念
k x l = σk σ k+1 …σ n －1 ,
其中 k ≤ l ≤ n 。
换言之 k x l 是带子x的一节，其从带子 x 的第(k+ 1)个符号开始跑，经过了 l个符号。很明显， k x l 带子的长度是 1-k 。我们会同意说如果 k = l ，而且 k x l = Λ ，这个带子的长度就是 0。作为该概念的一个有用属性，我们有
x = 0xk kxn ,
这里 k ≤ n，或者更一般的说
kxm = kxl lxm
其中 k ≤ l ≤ m ≤ n
我们应当把这种 0x k 一样的带子用初始节（the initial section ）或 x带子之长度为k的部分。
对 n 次相乘的 xxx…x ，标记为 xn 也能用于约定 x0 = Λ 。
解释了所有关于要输入机器的带子的概念，我们现在转到一自动机的形式化定义。
定义 1 字母系统 ∑ 之上的 一个（有穷）自动机一个系统 Д=(S,M,s0,F), S 是一个有限非空集（ 系统Д 的内部状态），M 是一个定义在“其状态对和带有S 中的值之符号 ”笛卡尔积 S × ∑ 上的函数，s0 是 S 的元素（Д 的初始状态）， F 是S 的子集（ Д 的指定最终状态 ）。
使 Д 是一台自动机。 首先函数 M 可以一种非常自然的方式通过一个来自如下定义的递归，从 S × ∑ 被扩展到 S × T ：
M(s, Λ ) = x, 对 s 在 S 中;
M(s,xσ) = M( M(s,x),σ ) ，对 S 中的 s，以及 T 中的 x, ∑中的σ 。
（ 译注：s 是“系统 Д 的内部状态，有限非空集”S 的元素，x 属于总带子类型T 的一种， 符号 σ 属于有穷字母系统∑。）
M(s,x) 的意义非常简单：它表示通过以状态 s为初始而得的机器状态（it is that state of the machine obtained by beginning in state s），并且一个符号接着一个符号的阅读整个磁带 x，根据给定的移动表来改变状态。应当从刚给出的对 M 的扩展定义立即变的明显， 我们有如下的有用属性：M(s,xy) = M(M(s,x),y)，对 S 中的所有 s，以及 T 中的 x,y (译注：指 s 是“系统Д 的内部状态，有限非空集”S 的元素， x ，y 属于总带子类型 T 的一种 )。
我们现在可以容易的定义那些引发了自动机给出一个“是”回答的磁带集合。
定义2. 带子集通过 在符号 T(Д) 中的自动机 Д，去 接受或者说去定义在 T 中的所有带子x，从而M(so,x)在 F 中。(译注：F 是S 的子集， Д 指定的最终状态 ）。
定义3. 带子的所有可定义集的种类，在符号 ? 中，是所有对于某些自动机 Д，其形式是 T(Д) 的集合之聚集。
接受（acceptance）的意义可以用一个图来说的更清楚。设 x = σ0 σ1 . . . σn-1 。对每个 k ≤ n,设 M(s0，0xk )
从而对 k > O ，我们有 sk = M ( sk-1 ，σ k-1 ) 。
带子 x 处在 T(Д)中的条件是， S 的元素 sn 是在 F 中。各个 sk 是自动机 Д 在读取了带子 x 中第 k 个符号后的状态。因此如果写了下面的图：
σ0 σ1 σ2 . . . σn-1
s0 s1 s2 s3 . . . sn-1 sn ，
我们就有了关于自动机 Д 在带子 x 上移动的完整图片。在这个图片中非常重要注意的一点是，“较之带子上的符号数， 内部状态多了一个（there is exactly one more internal state than there are symbols on the tape）”，这个事实会在节4多次使用到。
2. 可定义集的数学刻画（A mathematical characterization of definable sets）
一台自动机可以是非常复杂的对象，而且不是非常清楚“通过自动机去定义的集合可以变的多么复杂（how complicated the sets definable by automata can become）”。为理解这些可定义集的特性，我们将在本节发展出“可对这些集合的本质作刻画”的一种数学上的简单完备，其精确的显示了考虑“仅有一个有限量内部状态的机器（machines with only a finite number of internal states）”的完全效果。这种“有限性（finiteness）”条件肯定是我们研究的主要特性。
实际将给出两个不同的刻画，但是它们共享涉及到“所有带子的集 T 的相等关系（involving equivalence relations over the set T of all tapes）”的一个通用特性。假设读者熟悉等价类和等价关系的概念。
定义4. 在 带子的集合 T 上的一个等价关系 R 有右不变性（right invariant），如果无论何时 xRy ，则对在 T 中所有的z ，有 xzRyz.
显然有一个类似的左不变性相等关系（left-invarinnt equivalence relations）的定义 。
定义5. 集合 T 上的一个相等关系，如果既是有右不变性的，又是有左不变性的，就是一个全等关系（a congruence relation ）。
如果 R 是全等关系，那么公式 xRz 和 y Rw 总必然包含 xyRzw 。在全等中，如果 [x]是包含了 x 的相等类， [y] 是包含了y 的相等类，然后我们就可以通过以下等式分类，去定义两个公式之无歧义乘积（the product of the two equivalence classes by the equation）
[x][y] ＝ [x y ]
数学术语，等价类的集合（the set of equivalence classes）被说成是“在全等关系 R 下的 T 之半群的系数（the quotient semigroup of T under the congruence relation R ） ”， 并被说成是 T 的一个“同态像（ a homomorphic image ）”。T 有许多独立的同态图，但我们最关心的是那些有穷的同态图。某种程度上更一般的我们应当使等价关系去满足以下定义。
定义6. 如果在 T 上的一个等价关系下，仅有有穷多的等价类，那么 T 上的该等价关系索引有穷（An equivalence relation over T is of finite index if there are only finitely many equivalence classes under the relation.）。
有这些定义， 我们现在可以陈述刻画可定义集的第一个结果。该定理是来自 J. R. Myhill 而且有他令人感激的允许。
定理1. （Myhill）设 U 是带子集。下面三个条件是等价的：
(i)U 在 ? 中；（译注：? 见定义3）
(ii)U 是有限索引 T 上的一个全等关系之某些等价类的联合 ；
(iii)显式全等关系 ≡ 是通过以下条件定义的：对在 T 中的 所有 x,y ， 当且仅当“ z,w 在 T 中， 无论何时 zxw 是在 U 中，
则 zyw 是在 U 中” 时 x ≡ y ，反之则是有限索引的全等关系(a congruence relation of finite index)。
证明：假设(i)以及特别的 对一个适当的自动机Д ，U = T(Д)。 通过条件 xRy 定义一个关系 R ，当且仅当对如果 M(s, x) = M(s, y) 对所有属于 S 的 s 。很明显 R 是一个等价关系， 但其也是一个全等关系。假设 xRy 和 z 是 T 中任意的带子。然后
对所有属于状态 S 的元素s, 有
M(s,xz) = M(M(s,x),z)
= M(M(s,y),z)
= M(s,yz)
因此 R 就是右不变性的(译注: 类似 xz = yz 可得到z在等式中的右不变性)。 又如:
对所有属于状态 S 的元素 s
M (s,zx) =M(M(s,z),x )
=M(M(s,z),y )
=M(s,zy),
从而 R 被显示有左不变性 (译注: 类似 zx = zy 可得到z在等式中的左不变性)。
“R 是有限索引(R is of finite index)”是以下事实的结果：如果 x 是一条固定的带子 而且 r 是自动机 Д 的内部状态数量，则表达式 M(s,x)可以呈现最多r 个不同值（if x is a fixed tape and r is the number of internal states of Д, then the expression M(s,x) can assume at most r different values）。因此等价类的数量最多是 rr 。
最后如果 x 是在T(Д)中且 xRy ，则 M(s0,x) = M(s0,y) ，从而 y 也是在T(Д)中。这个评论显示了 U = T(Д) 实际上是“处在 ‘有关 U 中的带子’ 关系 R 下的等价类的联合（the union of the equivalence class under R of those tapes in U）”。我们因此显示了 (i)蕴含了 (ii)。
下一个假设就是有（holds）陈述 (ii)，设 R 现在表示满足(ii)中提到的条件 的任何全等关系。在术语 U 中考虑 (iii) 中定义的特定关系。让 x 和 y 可以是任何使得 xRy 成立的带子。假设 zxw 是在 U 中。现在 R 是一个全等关系，所以 zxw Rzyw 。另一方面使得 U 是等价类的集合。从而 zyw 必需也在 U 中。该论点实际显示了如果 xRy, 那么 x ≡ y 。 换言之， = 是一种较之关系R 而言，作出更少区分的符号（ = is a relation making fewer distinctions than the relation R ）。 ≡ 是一个全等关系，是其定义的无足轻重的结果，所以如果 R 是有穷索引， 那么 ≡必当也需要是有限索引的( That ≡ is a congruence relation is a trivial consequence of its definition, so if R is of finite index, then ≡ must necessarily be of finite index too)。因此， (ii)蕴含了 (iii)。
最后，假设有(iii)。我们必需定义一台自动机 Д 从而 U = T(Д)。为了这个目的，设 S 是在全等符≡下的等价类的集 。通过公式来定义函数M。
M ( [ x ] , σ ) = [ xσ ]
其中方括号显示了等价类的构造（the square brackets indicate the formation of equivalence classes）。注意我们只需要“ ≡ 是有右不变性”的这个事实去看出 “ M 的定义 无歧义（the definition of M is unambiguous）”。进一步的，设 so = [Λ]， 并最后让 F 成为“所有[x]的集合,其中x 是在 U 中”。应当很明显的是 U 实际上是≡下的一个等价类的联合。一个简单的归纳论据（inductive argument）显示了 如果 M 以“在节1中显示的”方式扩展到 集合 S × T ， 那么对属于T 的所有x , y ，有M([x],y) = [xy]。因此我们立刻可以看到 “在 F 中有 M(s0 ,x) = M([Λ],x ) = [x] ，当且仅当 x 在U 中 ”；换言之 ,就像显示出来的， U = T(Д) 。因此，(iii) 蕴含了(i)，且定理1的证明结束了。
定理1的主要麻烦在于“在关系 ≡下的等价类的数量会变的非常大，如同证明中(i)蕴含了(ii)中所显示的”。为了更加经济而且和定义了集 U 简单自动机靠的更近，相对于要求全等关系而言，就应当仅仅使用右不变性等价关系。以下用“在一个对定理1精确并行风格下表示的”去把定理公式化（The following theorem is formulated in an exactly parallel fashion to Theorem 1），且该定理本质上是对由 A. Nerode5 作出的一个理论简化。其使用了一个某种程度上较之这里采用的概念，更深的涉及到自动机概念。该原理非常的有用，且被 J. C. Shepherdson7 用来作为一个对节七中主要定理的证明，将在这里得到解释。
定理2. (Nerode) 设 U 是带子集。
下面三个条件是等价的：
(i) U 在 ? 中； （译注：? 见定义3）
(ii)U 是某些有右不变性的和存在有限索引的 T上的等价关系的等价类之联合 。
(iii) 显式右不变性等价关系 ≡ 是由以下条件 定义的：对所有在 带子集T 中的x ,y ，当且仅当“对T 中的所有 z ，无论何时 xz 是在 U 中，然后 yz 就在 U 中了”则 x E y ，反之则是有限索引的全等关系 （for all x ,y in T, x E y if and only if for all z in T, whenever xz is in U, then yz is in U ）”。
不需要对此给出详细的证明，因为几乎和定理1同证（it can be copied almost word for word from the proof of Theorem 1）。仅仅需要提的是在证明 (i)蕴含了 (ii)的关系 R 中有更简单的定义：
当且仅当 M (s0,x) = M (s0,y)时， x R y 。
这显示了对关系 R 而言，等价类型数量最多是状态机 Д 的内部状态的数量 。这种对完全证明的标记和分析直接导致了以下推论。
推论2.1. 如果 U 是在 ? 中， 则关系 E 下等价类的数量就是任何定义在U 下的自动机内之部状态中的最小量。
(Corollary 2.1. If U is in 3, then the number of equivalence classes under the relation E is the least number of internal states of any automaton defining U )
换言之， 关系E 立刻就带到了最经济的由 U 定义的自动机。这个评论也是由 Nerode 给出的。
作为定理1的一个简单应用，我们将看到所有形如 0n10n ， n = 0,1,2,…的带子之集 U ，是不可以被任何自动机定义的（is not definable by any automaton）。假设和“ U 是在 ? 中”相反。考虑定理1 (iii) 的 ≡ 关系。该关系将是有限索引的，从而对某些整数 n ≠ m ，我们将会有 0n ≡ 0m 。这就 立即得到 0n1 0m ≡ 0n1 0n ，因此 0n1 0m 在带子集 U 之中，这是不可能的。因此 U 不可能是在 ? 中。
3. 可定义集的类型之闭包属性（Closure properties of the class of definable sets）
使用在前序节中给出的定理，我们可以衍生出关于类? 的一些非常简单的事实。结果就是 ? 可以实际上通过“其在某些带子集上的自然操作下之闭包属性 （by its closure properties under some natural operations on sets of tapes）”来刻画，但是关于这个事实的讨论将在节6中作出。有时候更容易使用定理1和定理2，另外一些时候更容易给出机器的直接构造。在本节我们将显示布尔操作是如何在这两种方式中得以完成的。第一次，我们看上虽然是通过直接方法，更容易的证明了两个定理。
定理3. 如果 x 是在 T 中，那么 仅仅由 x 组成的{x}就是在 ? 中。
证明：明显的一台自动机可以被构建出来，其识别有一个且仅有一个预先给出的带子；然而， 定理2更容易应用。 定义在定理2 (iii) 中的关系 E ，以术语 U = {x} 简单的表示说， 当且仅当“无论何时 y 和 z 都是带子 x 的初始段”时 yE z，则 y = z 。因此关系 E 对 x 的每个初始段就有一个等价类 ，以及对带子的所有剩下部分有一个额外的等价类。很明显 E 之后就是有限索引的了，这完结了该证明。
如果 x 是任何带子，那么它就可以颠倒过来并向回写（can be turned end-for-end and written backwards）。设 x* 表示回写 x 的结果，从而如果 x = σ0σ1 . . . σn-1 ，那么 x* ＝ σn-1 σn-2 . . . σ0 。很明显我们有以下规则：
σ0 = σ, 对在 ∑ 里面的 σ ，
Λ* = Λ ，
x** = x ,
而且，
(x y)* ＝y* x*
在“U 是任何带子集 ”情况下，U* 标记了 所有 x* 的集合，其中 x 是在U 中。
一台自动机的移动，根据节1的定义，总是从左到右。因此从最初的定义开始，以下的结果就有点儿令人惊讶了。
定理4. 如果 U 是在 ? 中,那么 U * 也在 ? 中。
证明：该定理的内容是说，如果一个带子集合是可定义的话，那么“通过往回写所有定义的带子获得的集合（the set obtained by writing all the defined tapes backwards）”也是可以定义的。从一台给出的定义了 U 的机器去直接构建一台定义 U * 的机器 相当的冗长，但是定理1使得结果几乎是很明显了。设 ≡ 是通过来自定 理1 (iii) 术语 U 定义的关系，并使得 ≡* 成为类似于 U * 的关系。假设 x ≡* y 。如果 zx*w 是在 U 中，那么（zx*w ）* 是在 U* 中。但是 （zx*w ）* ＝ w* x z*。因此， w* y z* 也在 U * 中；但是 w* y z* ＝ （z y*w ）* ，而且zy*w 也在 U * 中。这显示出 x* ≡ y* 。因为 U ** = U ， 所以U 和 U * 的互换论点也是正确的（Since U ** = U ,this argument with U and U * interchanged is also valid）， 而且我们证明了：对在 T 中的所有x,y ，当且仅当 x* ≡ y* ，则x ≡* y 。然后就清楚了，如果 ≡ 是有限索引的，那么 ≡ 必需也是带“相同数量的等价类（the same number of equivalence classes）”的有限索引，证毕。
定理5 类 ? 是一个布尔代数的集合。
证明：“类 ? 在补下是闭的”是最明显的事实，即便从原始定义开始也是如此。对如果 U = T(Д) 其中 Д = (S,M,s0, F )，那么 T – U = T(￡ ) ， 其中 ￡ = (S,M,s0, S ? F ) 。还仅需要证明的一个是 T 在交集下是闭的。假设 U1 和 U2 是在 ? 中。由定理2， 设 R1 和 R2 是两个有右不变性的有限索引等价关系，比如对 i = 1, 2 ， U i 是在关系Ri 中的等价类之一个联合。考察等价关系 R3 = R1 ∩ R 2 ，换句话说就是， x R3 y 当且仅当 x R1 y 且 x R2 y 。 R3 当然就是有右不变性的。在关系 R 下的每个等价类，是关系 R1 和 R2下的等价类的一个交集。因此，对关系 R3 的等价类数量，最多就是 R1 和 R2 数量的乘积。然后我们就看到， R3 是有限索引。现在 U1 ∩ U2 ，是两等价类交集简单的一个联合，从而 U1 ∩ U2 是在关系R3 下面的等价类的联合，通过定理2，其显示了 U1 ∩ U2 是在 ? 中。证毕。
推论5.1. 类 ? 包含了所有带子的有限集(The class ? contains all finite sets of tapes)。
其是定理3和定理5的直接结果。
定理5的证明可能看上去太抽象了。为了把它弄的更直接点，我们接下来将显示如何立即形成一台定义该交集的机器。
定义7. 设 Д = (S,M,s0, F)且 ￡ =(T,N,t0,G) 是两台自动机。Д × ￡ 的直接乘积是自动机 (S × T,M ×N,(so,to), F × G) 其中 S × T 和F × G 是集合的笛卡尔积，(so,to) so 和 to 的序列对，在 S × T )× ∑ 上的 函数 M ×N 是由如下公式定义的
(M × N) ((s,t),σ) = (M(s,σ),N(t,σ))
对所有处于状态S 中的元素 s ，以及所有处于状态 T 中的元素t，以及 所有处于字母系统 ∑中的 字母σ 。
索引 （References）
1. A. W. Burks and Hao Wang(王浩),
自动机逻辑
“The logic of automata,”
Journal of the Association for Computing Machinery, 4,193-218 and 279-297 (1957).
2. S. C. Kleene,
神经网络和有限自动机中表现事件
“Representation of events in nerve nets and finite automata,”
Automata Studies, Princeton, pp. 3-4 1,
(1956).
3. W. S. McCulloch and E. Pitts,
神经活动中将临的一个逻辑运算观念
“A logical calculus of the ideas imminent in nervous activity,”
Bulletin of Mathematical Biophysics, 5, 115-133 (1943).
4. E. F. Moore,
在序列机上的思想实验
“Gedanken-experiments on sequential machines,”
Automata Studies, Princeton, pp. 129-153 (1956).
5. A. Nerode,
线性自动机转换
“Linear automat on transformations,”
Proceedings of the American Mathematical Society, 9, 541- 544 (1958).
6. E. Post,
递归不可解问题的一个变异
“A variant of a recursively unsolvable problem,”
Bulletin of the American Mathematical Society, 52, 264-268 ( 1946).
7. J. C. Shepherdson,
双向自动机规约为单向自动机
“The reduction of two-way automata to one-way automata,”
IBM Journal, 3, 198-200 (1959).
pending 11.17 evening
(未完)