线性有界自动机 图灵机 计算能力比较 图灵机等价于0型文法，对应所有递归可枚举语言的集合；线性有界自动机（LBA）等价于1型文法，对应所有上下文有关语言（CSL）的集合。所以题主的两个问题实质上是同一个问题，而这个问题的答案是：1型文法严格包含于0型文法。现在我们构造一个递归的但不是CSL的语言，方法是经典的对角化方法。设所有的 CSL 可枚举为 G_1，G_2，.，给定一个字母表∑，设 x_1，x_2，.是∑*的一个枚举，定义语言L={ x_i|x_i 不可由文法 G_i 生成 }，则 L 不是 CSL，否则 L 可由某个文法 G_j 生成，此时考虑 x_j 是否属于 L，可发现矛盾。但 L 是可判定的，因为 CSL 的成员判定问题是 PSPACE-complete 的。
图灵机是必须的么？
编译原理中，自动机究竟是什么. 自动机是有限状态机(FSM)的数学模型。FSM 是给定符号输入，依据(可表达为一个表格的)转移函数“跳转”过一系列状态的一种机器。在常见的 FSM 的“Mealy”变体中，这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。逐个读取输入中的符号，直到被完全耗尽(把它当作有一个字写在其上的磁带，通过自动机的读磁头来读取它；磁头在磁带上前行移动，一次读一个符号)。一旦输入被耗尽，自动机被称为“停止”了。依赖自动机停止时的状态，称呼这个自动机要么是“接受”要么“拒绝”这个输入。如果停止于“接受状态”，则自动机“接受”了这个字。在另一方面，如果它停止于“拒绝状态”，则这个字被“拒绝”。自动机接受的所有字的集合被称为“这个自动机接受的语言”。自动机 automaton 原来是模仿人和动物的行动而做成的机器人的意思。但是现已被抽象化为如下的机器。时间62616964757a686964616fe78988e69d8331333337613234是离散的（t=0，1，2…），在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时刻的内部状态所。
请问什么是形式语言与自动机 形式语言 形式语言 是一个字母表上的某些有限长字串的集合。一个形式语言可以包含无限多个字串。语言的形式定义 字母表∑为任意有限集合，ε 表示空串，记∑0 为{ε}，全体。
有限状态机与有限状态自动机的区别是什么？
关于图灵机和有穷自动机 1.一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0，1，2，.，纸带的右端可以无限伸展。2.一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。3.一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。在某些模型中，纸带移动，而未用到的纸带真正是“空白”的。要进行的指令(q4)展示在扫描到方格之上在某些模型中，读写头沿着固定的纸带移动。要进行的指令(q1)展示在读写头内。在这种模型中“空白”的纸带是全部为 0 的。有阴影的方格，包括读写头扫描到的空白，标记了 1，1，。
