自动机

词语 : 语言学术语 : 数学与应用数学 : 物理学类 : 计算语言学 : 软件 : 互联网 : 通信工程 > 自动机

·形式描述	·有限自动机的分类	·有限自动机的扩展
·有限状态自动机的最小化	·计算能力与判定问题	·百科辞典
·英文解释	·近义词	·相关词
·包含词	·更多结果...

形式描述

　　对信号序列进行逻辑处理的装置。在自动控制领域内，是指离散数字系统的动态数学模型，可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
　　自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有：有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。

有限自动机的分类

　　下面是三类有限自动机
　　确定有限自动机(DFA)
　　　自动机的每个状态都有对字母表中所有符号的转移。
　　非确定有限自动机(NFA)
　　自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是「未定义」的，自动机因此不知道如何继续读取输入，则拒绝这个字。
　　有ε转移的非确定有限自动机(FND-ε或ε-NFA)
　　　除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外，它们可以做根本不关于符号的跳转。就是说，如果一个状态有标记著 ε 的转移，则 NFA 可以处在 ε-转移可到达的任何状态中，直接或通过其他有 ε-转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 ε-闭包。
　　尽管可以证明所有这些自动机都「可以接受同样的语言」。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。

有限自动机的扩展

　　上述自动机接受的语言家族被称为正则语言家族。更强力的自动机可以接受更复杂的语言。比如:
　　下推自动机(PDA)
　　这种机器等同于 DFA (或 NFA)，除了它们额外的装备了栈形式的内存。转移函数 δ 也依赖于在栈顶的符号，并在每次转移时指定如何变更栈。非确定 PDA 接受上下文无关语言。
　　线性有界自动机(LBA)
　　LBA 是有限制的图灵机；不使用无限磁带，它的磁带有同输入字元串成正比的空间。LBA 接受上下文有关语言。
　　图灵机
　　它们是最强力的电脑器。它们拥有磁带形式的无限内存，和可以读取和变更磁带的磁头，它可在磁带上向任何方向移动。图灵机等价于演算法，是现代电脑的理论基础。图灵机判定递归语言并识别递归可枚举语言。

有限状态自动机的最小化

　　根据 Myhill-Nerode定理，在同构意义下接受一个正则语言的最少状态的确定有限状态自动机是唯一的。同时我们还存在有效的演算法（时间开销是O(n2)的）构造出与给定确定有限状态自动机等价的最小化的确定有限状态自动机。

计算能力与判定问题

　　确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质，许多为其他自动机（下推自动机或图灵机）不能判定的问题，在有限状态自动机的情形下，都可以得到判定，并且存在有效的演算法。
　　对一个确定有限状态自动机，下述判定问题都可以判定，并且存在有效的演算法。
　　该自动机识别的语言是否为空集。
　　该自动机识别的语言是否为有限集。
　　该自动机是否与另一个确定有限状态自动机识别同一个的语言。

百科辞典

　　zidongji
　　自动机
　　automata
　　　　对信号序列进行逻辑处理的装置。在自动机理论中主要是指抽象自动机。抽象自动机是用来表示逻辑关系的动态数学模型，一般都是指能变换和处理信息的离散系统的动态数学模型。在自动控制领域内，自动机是指离散数字系统的动态数学模型，它可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计、乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。
　　　　自动机的组成和特点自动机起源于20世纪30年代的图灵机,一般都有以下3个组成部分：①输入设备：又称传感器或变送器，相当于生命有机体的感受器，用来接受外界的信息。②输出设备：又称执行器，相当于生命有机体的效应器，用来向外界输出信息，执行各种操作，实现信息的效用。③中央处理器：又称调节器或控制器，相当于生命有机体的神经系统，用来处理、存储和传递信息。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
　　　　自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。当自动机与环境进行信息交换时，输出不仅决定于输入，而且也决定于自动机的内在状态。自动机通过内在状态来记忆过去的输入，新的输入又反映在新的内在状态中，因此内在状态起着内存储器的作用。自动机的这种信息变换规律表明，一个自动机可用一个五元组表示:A＝(□,□,□,□,□)。式中□、□ 和□分别是状态集、输入集和输出集,□和□分别是状态转移函数和输出函数,即映射 □:□×□→□和□:□×□→□。自动机的行为也可以用状态转移图即状态图来表示 (见图自动机□的状态图)。状态图是一种有向图。用节点表示状态，箭头表示状态转移的方向，箭头旁的字符或数字表示输入或输出，视箭头对于节点的向背而定。A能识别 {□∈{0,1}|□ 以11结束且无连续0｝。
　　　　自动机分类自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有以下几类:①有限自动机和无限自动机。如果□,□,□都是有限集，则称□为有限自动机，又称时序机。如果□,□,□中有一个是无限集,则称□为无限自动机。有限自动机是时序网络和一切序储量有限的离散系统的数学模型，如神经网络和语言识别器等。②线性自动机和非线性自动机。如果□ 和□ 均是线性函数,则称□为线性自动机,否则称□为非线性自动机。线性自动机便于用线性时序电路来实现,在编码网络、通信网络和计算机控制系统中应用甚广。③确定型自动机和不确定型自动机。如果自动机 A下一内在状态可由当前的输入和当前的内在状态所完全决定，则称A为确定型自动机，否则称A为不确定型自动机。概率自动机和模糊自动机均属于不确定型自动机。概率自动机是指自动机所处环境或其内部有随机因素的

英文解释

: automata
n.: automat, Automaton, automatons, robot

近义词

自动装置