确定有限状态自动机

基础概念定义确定有限状态自动机A{displaystyle{mathcal{A}}}是由一个非空有限的状态集合Q{displaystyleQ}一个输入字母表ΣΣ-->{displayst

构成一个标准的细胞自动机（A{displaystyleA}）由元胞、元胞状态、邻域和状态更新规则构成。用数学表示为：其中L为元胞空间；d为元胞自动机内元胞空间的维数；S是元胞有限的、离散的状态集合；

词源Automaton一词源于古希腊语：αὐτόματος（automatos），意为“以自我意志动作”。运用摆钟音乐盒自动人偶（英语：Automaton，又称机器人偶）：在人偶内部，设置多个特殊形状的齿轮、随动机械零件，形成精密复杂的构造；上紧发条后，随动机械元件会因为齿轮的转动，而带动人偶手臂，使人偶自己做出类似人类的动作，例如写字、弹琴、表情变化等；自动人偶的制造，可追溯到18世纪到19世纪欧洲，有些是出自于巧夺天工的钟表工匠之手，可以说是“古代的机器人”以及“现代机器人的前身”，但无法像人工智能一样拥有自我思考，甚至是情感意识。人偶钟（英语：Automatonclock）手动机械表《写字的皮耶尔》LéopoldLambert1900年，人偶右手俐落地似写字般移动，眼睛变化像是带着睡意。当头部低垂灯火减弱时，又会宛如回神继续写信。（野坂自动人偶美术馆（日语：野坂オートマタ美術館）收藏...

概念和术语状态存储关于过去的信息，就是说：它反映从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述。有多种类型的动作：FSM（有限状态机）可以使用上面图1那样的状态图（或状态转移图）来表示。此外可以使用多种类型的状态转移表。下面展示最常见的表示：当前状态（B）和条件（Y）的组合指示出下一个状态（C）。完整的动作信息可以只使用脚注来增加。包括完整动作信息的FSM定义可以使用状态表。除了建模这里介绍的反应系统之外，有限状态自动机在很多不同领域中是重要的，包括电子工程、语言学、计算机科学、哲学、生物学、数学和逻辑学。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。分类有两个不同的群组：接受器／识别器和...

基本描述自动机是有限状态机（FSM）的数学模型。FSM是给定符号输入，依据（可表达为一个表格的）转移函数“跳转”过一系列状态的一种机器。在常见的FSM的“米利型有限状态机”（Mealy）变体中，这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。逐个读取输入中的符号，直到被完全耗尽(把它当作有一个字写在其上的磁带，通过自动机的读磁头来读取它；磁头在磁带上前行移动，一次读一个符号)。一旦输入被耗尽，自动机被称为“停止”了。依赖自动机停止时的状态，称呼这个自动机要么是“接受”要么“拒绝”这个输入。如果停止于“接受状态”，则自动机“接受”了这个字。在另一方面，如果它停止于“拒绝状态”，则这个字被“拒绝”。自动机接受的所有字的集合被称为“这个自动机接受的语言”。但要注意，自动机一般不必须有有限数目甚至可数个状态。比如，量子有限自动机有不可数无限个状态，因为所有可能状态的集合是在复投...