[科普中国]-线性有界自动机

线性有界自动机是一种图灵机，是把计算限制在仅仅包含输入的那一段带上的图灵机。可用作上下文有关语言的识别接受器。

简介线性有界自动机是一种图灵机，是把计算限制在仅仅包含输入的那一段带上的图灵机。可用作上下文有关语言的识别接受器。

线性有界自动机（缩写为LBA）可形式地由 来表示。其中：K 是状态的有限集；Γ 是带符号的有限集；是输人符号集；K 中的 q0是起始状态；是终结状态集；δ 是从到 子集的映射，(L,R)分别是读写头左右移一格。Σ含有两个特殊的符号，通常记为 Ȼ 和 $ ，它们分别是左端标志和右端标志。这些符号开始就处在输入带的端点，其作用是阻止带头离开带上出现符号的区。

辨析确定型和非确定型图灵机接受的语言是相同的。

非确定型线性有界自动机（以 NDLBA 表示）接受的语言类正好是上下文有关语言。

确定型线性有界自动机（以DLBA 表示）的功能不会超过 NDLBA 的，以不等式表示为

其中 L 表示该类自动机接受的语言集合。至今人们仍为能把包含关系精确为真包含关系或相等关系。这是一个著名的尚未解决的问题，简称 LBA 问题。1

图灵机图灵机，又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学