自动机(卷名：自动控制与系统工程)
automata
对信号序列进行逻辑处理的装置。在自动机理论中主要是指抽象自动机。抽象自动机是用来表示逻辑关系的动态数学模型，一般都是指能变换和处理信息的离散系统的动态数学模型。在自动控制领域内，自动机是指离散数字系统的动态数学模型，它可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计、乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。
自动机的组成和特点 自动机起源于20世纪30年代的图灵机,一般都有以下3个组成部分：①输入设备：又称传感器或变送器，相当于生命有机体的感受器，用来接受外界的信息。②输出设备：又称执行器，相当于生命有机体的效应器，用来向外界输出信息，执行各种操作，实现信息的效用。③中央处理器：又称调节器或控制器，相当于生命有机体的神经系统，用来处理、存储和传递信息。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。当自动机与环境进行信息交换时，输出不仅决定于输入，而且也决定于自动机的内在状态。自动机通过内在状态来记忆过去的输入，新的输入又反映在新的内在状态中，因此内在状态起着内存储器的作用。自动机的这种信息变换规律表明，一个自动机可用一个五元组表示:A＝(S，X，Y，f，g)。式中S、X 和Y分别是状态集、输入集和输出集,f和g分别是状态转移函数和输出函数,即映射 f:S×X→S和g:S×X→Y。自动机的行为也可以用状态转移图即状态图来表示 (见图)。状态图是一种有向图。用节点表示状态，箭头表示状态转移的方向，箭头旁的字符或数字表示输入或输出，视箭头对于节点的向背而定。A能识别 {x∈{0,1}|x 以11结束且无连续0｝。自动机分类 自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有以下几类:①有限自动机和无限自动机。如果S，X，Y都是有限集，则称A为有限自动机，又称时序机。如果S，X，Y中有一个是无限集,则称A为无限自动机。有限自动机是时序网络和一切序储量有限的离散系统的数学模型，如神经网络和语言识别器等。②线性自动机和非线性自动机。如果f 和g均是线性函数,则称A为线性自动机,否则称A为非线性自动机。线性自动机便于用线性时序电路来实现,在编码网络、通信网络和计算机控制系统中应用甚广。③确定型自动机和不确定型自动机。如果自动机 A下一内在状态可由当前的输入和当前的内在状态所完全决定，则称A为确定型自动机，否则称A为不确定型自动机。概率自动机和模糊自动机均属于不确定型自动机。概率自动机是指自动机所处环境或其内部有随机因素的自动机。1956年C.E.香农首先把自动机拓展为概率自动机，并证明概率自动机的信息处理能力与有限自动机等价。1968年E.S.桑托斯把自动机拓展为模糊自动机，作为图像识别和学习系统的模型，并证明模糊自动机的识别能力与有限自动机等价。④同步自动机和异步自动机。如果自动机A的状态转移和输出变化均与中央时钟信号同步,即可把时间划分成相等的时间间隔，则称 A为同步自动机。如果自动机 A从一个状态转换到另一个状态的瞬间不能预先确定,即要把时间划分成不相等的时间间隔,则称 A为异步自动机。在许多情况下只要引用抽象自动机时间就可以把异步自动机化为同步自动机来研究。⑤级联自动机和细胞自动机。多台自动机用串联、并联或串并联的方式连接起来，就成为级联自动机。大量的元自动机通过邻域连接方式连接起来，就成为细胞自动机。动态细胞自动机（又称 L系统）可以作为生命体的生长发育模型。
参考书目
C.E.申南、J.麦克卡赛编，陈中基编译：《自动机研究》，科学出版社，北京，1963。(C.E. Shannon and J.McCarthy (eds), Automata Studies，Princeton University Press, Princeton, N.J.,1956.)