Question

自动机理论的详细内容

Answer 1

常见自动机有以下几种：以电话交换机为主要实例的有限自动机，是自动机理论的基础，被应用到自动控制，生物系统中；由下推表组成的单项非确定程序的下推自动机；线性有界自动机；用来描述通用计算机计算能力的图灵机模型；进行与转移函数，转移状态有关输出的时序机；由一些基本语句构成程序框图的波斯特机；随即存储机；堆栈自动机；不受有限自动机做控制器和存储限制的无限自动机；统计自动机某一条件概率分布的概率自动机和细胞自动机。
数理语言学中研究抽象自动机的理论。抽象自动机是一种能够识别语言的抽象的装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统，这样的抽象自动机可以用来检验输入的符号串是不是语言中合格的句子，如果是合格的句子，自动机就接收它，如果不是，就不接收它。如图所示：
自动机可分为有限自动机、后进先出自动机、线性有界自动机、图灵机等几种。它们对语言的识别能力各不相同。