线性有界自动机

阐述

是一种被限制的 Turing 机，它不能将读写头移出输入所存在的区域，也即它的内存大小与输入大小相同。

性质

LBA 的组态数量是 $qng^n$，其中 $q$ 是状态数量，$g$ 是符号数量，$n$ 是输入长度。

由于它的组态数量非常有限，所以 $A_{\rm LBA}$ 是可判定的。

实例

性质

相关内容

参考文献