##### 自动机 - 自动机 - **自动机**是数字[[计算机]]的抽象模型, 是一种[[计算模型]], 也称为自动状态机, 即通过一组状态和状态间的转移规则来描述计算过程. 它能够模拟计算过程中的状态变迁, 输入处理和输出产生, 进而能够被用来形式化计算问题. 自动机与[[形式语言]]密切相关, 自动机的语言指自动机能够接受的[[字符串]]集合, 即一个形式语言. 根据自动机的类型不同, 所能接受的语言也有所不同. 状态转移函数是自动机的核心部分, 它决定了自动机如何根据字符串的每个输入字符变换状态, 不同类型自动机的状态转移函数不同 - $Q$ 状态集合, 自动机可能处于的一组有限状态 - $\Sigma$ 输入字母表, 可输入的有限符号集合 - $\delta$ 状态转移函数, 描述如何从一个状态转换到另一个状态 - $q_0$ 初始状态, 自动机的起始状态 - $F$ 接受状态集合, 如果最终停在这些状态之一, 则输入被接受 - 自动机与形式语言 - [[有限自动机]] [[正则语言]] - [[下推自动机]] [[上下文无关语言]] - [[线性有界自动机]] [[上下文相关语言]] - [[图灵机]] [[递归可枚举语言]]