_icon.png
){kind=icon}
_wordmark.png)
用户:LynChern/Sandbox：修订间差异
来自 LNN的:not(博客)？
更多操作
无编辑摘要 |
无编辑摘要 |
||
| 第1行： | 第1行： | ||
一个'''线性有界自动机'''（LBA）是一种抽象机器，它与[[Turing machine|图灵机]] | 一个'''线性有界自动机'''（LBA）是一种抽象机器，它与[[Turing machine|图灵机]]几乎相同，除了在给定输入的计算过程中，其磁头不允许移动到其无限磁带的有限区域之外，可访问的磁带单元数量是输入大小的线性函数。磁带本身具有无限长度，以适应任意长度的输入。（这个模型的一个等效替代版本为 LBA 提供不同长度的有限磁带，每个不同大小的输入对应一个磁带，磁带的长度是输入大小的线性函数。在这个替代版本中，有无限多个有限磁带供应，每个输入大小对应一个磁带。） | ||
与图灵机类似，LBA 是一个配备磁带的[[finite state machine|有限状态机]]。与图灵机系统不同，LBA 系统（有限状态机加上其磁带）对于每个输入只有有限多个系统状态；也就是说，对于每个输入，LBA 系统表现得像一个有限自动机。LBA 和 FSA 之间的一个关键区别是，FSA 的状态数量对于该 FSA 是固定的，而 LBA 的状态数量随着给定输入量的线性函数变化。 | |||
使用泵引理可以证明，存在一些语言，它们被某些 LBA 识别，但无法被任何[[push-down automaton|下推自动机]]识别。线性有界自动机识别[[context-sensitive language|上下文相关语言]]类。 | |||
==历史== | ==历史== | ||
Myhill（1960年）引入了 LBA，其动机是 Rabin 和 Scott（1959年）对有限自动机的研究。 | |||
==另见== | ==另见== | ||
* [[:Category:Linear bounded automata|线性有界自动机分类]] | * [[:Category:Linear bounded automata|线性有界自动机分类]]（本维基上具有与 LBA 同等能力的语言列表） | ||
==外部资源== | ==外部资源== | ||
2026年4月11日 (六) 01:20的版本
一个线性有界自动机（LBA）是一种抽象机器，它与图灵机几乎相同，除了在给定输入的计算过程中，其磁头不允许移动到其无限磁带的有限区域之外，可访问的磁带单元数量是输入大小的线性函数。磁带本身具有无限长度，以适应任意长度的输入。（这个模型的一个等效替代版本为 LBA 提供不同长度的有限磁带，每个不同大小的输入对应一个磁带，磁带的长度是输入大小的线性函数。在这个替代版本中，有无限多个有限磁带供应，每个输入大小对应一个磁带。）
与图灵机类似，LBA 是一个配备磁带的有限状态机。与图灵机系统不同，LBA 系统（有限状态机加上其磁带）对于每个输入只有有限多个系统状态；也就是说，对于每个输入，LBA 系统表现得像一个有限自动机。LBA 和 FSA 之间的一个关键区别是，FSA 的状态数量对于该 FSA 是固定的，而 LBA 的状态数量随着给定输入量的线性函数变化。
使用泵引理可以证明，存在一些语言，它们被某些 LBA 识别，但无法被任何下推自动机识别。线性有界自动机识别上下文相关语言类。
历史
Myhill（1960年）引入了 LBA，其动机是 Rabin 和 Scott（1959年）对有限自动机的研究。
另见
- 线性有界自动机分类（本维基上具有与 LBA 同等能力的语言列表）