自动机理论

自动机理论 【automata theory】【】 将离散数学系统的构造，作用和关系作为研究对象的数学理论。常见自动机有以下几种：以电话交换机为主要实例的有限自动机，是自动机理论的基础，被应用到自动控制，生物系统中；由下推表组成的单项非确定程序的下推自动机；线性有界自动机；用来描述通用计算机计算能力的图灵机模型；进行与转移函数，转移状态有关输出的时序机；由一些基本语句构成程序框图的波斯特机；随即存储机；堆栈自动机；不受有限自动机做控制器和存储限制的无限自动机；统计自动机某一条件概率分布的概率自动机和细胞自动机。