什么是有限自动机论?

什么是有限自动机论?

[拼音]：youxian zidongjilun

[外文]：finite automata theory

自动机论的次级学科，研究存储量有限的离散数字系统的功能和结构以及两者的关系。

自动电话交换机、开关网络和计算机等物理系统是存储量有限的离散数字系统的实例。有限自动机就是这种有限离散数字系统的抽象数学模型。有限自动机论的主要研究课题是分析和综合问题：给出一个具体的自动机或实现它的逻辑网络，分析有限自动机的功能描述;给出有限自动机的功能描述，综合出能实现此功能的有限自动机，并由此设计出满足要求的逻辑网络。具体内容有逻辑网络实现、状态化简、状态分配、神经网络、有限接收机和有限自动机的分解等。

发展简况

1938年美国科学家C.E.仙农等应用布尔代数对继电路接点电路进行研究，形成了开关网络理论，为有限自动机论的建立奠定了基础。电子数字计算机出现以后，由于对计算机进行逻辑设计的需要，开关网络受到人们普遍重视。50年代中期，美国科学家D.A.赫夫曼和E.F.莫尔各自独立地研究了时序网络理论，形成了有限自动机论的雏形。从此有限自动机论得到深入和系统的研究，已成为自动机论中一个较完整、较成熟的理论。

基本内容

有限自动机也称时序机。有限自动机的数学定义是:由输入集合X、输出集合Y、状态集合Q、状态函数δ与输出函数λ组成的抽象系统M(X，Y，Q，δ，λ)，其中 X、Y、Q 都是有限集合，δ和λ分别是Q×X 到 Q 和Q×X到Y上的单值函数。系统对时间来说是离散的，设在某一时刻t时系统处于某状态q∈Q，如果此时系统的输入为x∈X，则系统的输出为y＝λ（q，x），且在时刻t+1时，系统的状态变为q′=δ（q，x）。例如，一个自动机的输入集合为X＝｛0，1｝，输出集合为Y＝｛0，1｝，状态集合Q＝｛q0，q1，q2｝，其δ，λ函数如表1，表中第i行第j列处的内容是δ(qi，j)/λ(qi，j)。

可以用一个有向图来描述有限自动机，这个图叫有限自动机的状态图（图1）。图中有向弧上的标记为x/λ(q，x)。

上述有限自动机是定义在有限集合X 和Y上，但实际问题往往要求系统能处理集合X 和Y 中元素组成的序列。于是，进一步规定输入空序列时不改变有限自动机的状态，输出也是空序列；输入非空序列时的状态和输出为：依次输入序列中各元素后最终到达的状态和输出。这样就把函数δ和λ的定义范围扩大到由X和Y中元素组成的序列集合X*和Y*上。

前面定义的有限自动机，对于所有输入来说，在给定状态下都有唯一确定的输出和下步状态，因此也称完全定义的有限自动机，但实际应用中有时也考虑输出函数δ和状态函数δ对某些状态无定义的情形，人们把这种情形下的自动机称为不完全定义的有限自动机。另外，有时也考虑状态函数和输入函数取多值的情形，称为非确定型有限自动机。为了区别起见，把原定义的有限自动机称为确定型有限自动机。

逻辑网络

基本的逻辑元件按是否具有记忆功能，可以分为两类。一类是组合元件，如各种与、或、非门等，这类元件在时刻t的输入可以完全决定时刻t的输出。另一类元件是记忆元件，这类元件的输出不仅取决于元件的输入，而且取决于元件当前所处的状态，元件下一时刻的状态也由输入和状态决定。各种触发器和延迟器等都属于记忆元件。把一些基本逻辑元件按一定要求连接起来，就组成逻辑网络。如果把逻辑网络中进入记忆元件的输入线去掉后所得网络不再含有回路，则称这样的网络为合式网络。不含记忆元件的合式网络称组合网络。

组合网络不含记忆元件，所以网络在时刻t的输入可以完全决定它在时刻t的输出。如果组合网络的输入是x1，…，xk，输出是y1，…，yn，其功能可由下面方程组描述

yi＝f(x1，…，xk) (i＝1，2，…，n)

当所有组合元件都是二值元件时，此方程组就是描述组合网络功能的布尔方程组。在研究组合网络的分析与综合时，采用布尔代数或卡诺图等方法，把这种布尔方程组化简，设计出结构简单而又具有同样功能的组合网络。

一般逻辑网络含有记忆元件，其输出不仅取决于输入，而且取决于网络的内部状态，所以逻辑网络比组合网络复杂。但是，任何合式网络的功能都可以用一个有限自动机来描述;任何一个有限自动机所描述的功能，都可以用合式网络实现。在工程实现上，要求对于一个给定的有限自动机建立起实现此有限自动机的逻辑网络，为使建立的逻辑网络尽可能简单，人们自然考虑到有限自动机的化简和状态赋值等问题。

状态化简

在很多实际问题中，要求去掉有限自动机中起同样作用的状态，设计出功能相同而状态最少的系统。这个问题反映在理论上，就是有限自动机的化简问题。

M1和M2是两个有限自动机，若它们具有同样的输入集合和输出集合，q1是M1的一个状态，q2是M2的一个状态，如果q1和q2对所有的输入序列都有相同的输出，则说q1和q2是两个等价的状态。这里M1和M2可以是同一自动机，这时就有一个自动机的两个状态等价的概念。如果一个有限自动机的任意两个等价的状态必是同一状态，则说这个有限自动机处于最简形式。如果对于自动机M1的每一个状态，总有自动机M2的一个状态与之等价，反之，对于M2的每一状态，也总有M1的一个状态与之等价，则说有限自动机M1与M2等价。两个状态等价说明两个状态具有同样的功能，两个自动机等价说明两个自动机具有同样的功能。为使系统尽可能简单，人们当然对等价的最简形式的自动机感兴趣。有限自动机论已经证明：在同构的意义下，任何有限自动机都有与之等价的最简形式的有限自动机，并且这种最简形式的有限自动机是唯一的。根据有限自动机论，对给定有限自动机，可有效地求出与之等价的最简形式的有限自动机。

对于不完全定义的有限自动机，情形则复杂一些。相当于状态等价与自动机等价的概念，在不完全定义的有限自动机中有状态覆盖和有限自动机覆盖的概念。其他简问题就是求覆盖一个不完全定义的有限自动机的状态最少的完全定义的有限自动机。

状态分配

组成实际逻辑网络的基本元件一般是二值元件。要构造具有多个状态的网络，就要使用多个基本记忆元件，利用这些记忆元件的各种状态组合来表示不同的状态。例如，可用3个二值元件y1、y2、y3来表示具有5个状态的系统，对每一状态指定一组代表基本元件状态组合的编码（图2a）。

当然，把y1、y2、y3的编码分配给每一状态，可有多种不同的分配方案，图2b是另外一种分配方案。一般说来，不同的状态分配导致逻辑网络具有不同的复杂程度。如何选择较好的分配方案，使逻辑网络的构造尽可能地简单，这种状态分配问题也是有限自动机研究的主要课题之一。

对于异步逻辑网络，其状态分配问题主要是考虑状态转换上的稳定性，实现无竞争状态分配，因而与同步网络的状态分配有较大的差别。

神经网络

1943年W.S.麦克卡洛克和W.比脱斯提出了一个神经系统的模型。根据这个模型，神经系统的基本单位是神经元。每个神经元由细胞体、神经纤维和神经末梢组成，神经纤维是由细胞体发出的一个或数个神经末梢。有限个神经元连接在一起就构成了神经网络。在连接时，任一神经元的任一神经末梢只能同一个细胞体相接触。每一神经末梢只能有两种状态，即兴奋状态和抑止状态（图3）。兴奋神经末梢用黑点表示，抑止神经末梢用圆圈表示。这种神经网络模型是有限自动机的一个实际例子。S.C.克林尼于1951年在麦克卡洛克和比脱斯神经网络模型的基础上，提出了正则事件（正则语言）的概念，证明了正则事件是可以被神经网络或有限自动机表示的事件，而且神经网络或有限自动机可表示的事件也一定是正则事件。

有限接收机

在形式语言理论中，有限自动机通常作为语言的识别器来使用。这种有限自动机有一个特殊的状态q0，称初始状态。有一个特殊的状态子集F，称终止状态集合。主要研究在初始状态q0下，输入字符序列集合X*中的一个字符序列后所引起的状态转换，不考虑输出问题，这种有限自动机也称作有限接收机。按其下步状态是否完全确定，有限接收机分为确定型和非确定型两种，它们分别与确定型和非确定型有限自动机相对应。

若有限接收机M处于初始状态q0，对确定型有限接收机来说，如果对M输入字符序列x后，M最终达到的状态属于 F，则说M能接收字符序列x。对非确定型接收机来说，输入字符序列x后，M可达到的状态是依次输入x中各个元素后所有可能的状态集合;如果此集合中有一状态属于F，则说M能识别字符序列x。非确定型有限接收机和确定型有限接收机都接收同样一类语言，即正则语言。

参考书目

C.E.申南，J.麦克卡赛编，陈中基编译：《自动机研究》，科学出版社，北京，1963。(C.E.Shannon and J.McCarthy，Automata Studies，Princeton Univ.Pr.，Princeton，N.J.，1956.)M. A. Arbib， Theories of Abstract Automata，Prentice Hall， Englewood Cliffs， N.J.， 1969.