线性有界自动机中的标记定位
Marker positioning in Linear Bounded Automata
因此，我们最近在 class 中讨论了线性有界自动机的主题，但我们并没有正式定义它们。网上查了定义，还是搞不清楚marker的定位。它们是否总是应该位于输入字符串的两端？只要它们的距离至多是输入长度的某个常量倍数，它们能否更进一步到 left/right？如果是这样，我们是否可以分别为每个输入字符串选择它们的位置（例如，确保左侧标记始终位于输入字符串之前）？
线性有界自动机是非确定性图灵机的一种受限形式。限制是磁带是有限的。这是通过用 标记 限制磁带两端来确保的。仅此而已。
现在，您如何选择这些标记与自动机无关，因为与左右标记的距离（即磁带的长度）是输入长度的线性函数。
图灵机从一个磁带开始，磁带上“某处”写入了输入，磁带的头部指向它的第一个符号。 LBA 没有对此添加新的限制，因此它仍然存在：输入在某处。这意味着（由于限制标记）输入在两个标记之间 ，您可以将输入的第一个符号放在左侧标记之后，或者将输入的最后一个符号放在右侧标记之前标记。 LBA 的定义并不禁止这两种情况。
自动机如何使用磁带上输入的不同位置及其状态是另一个话题。换句话说，您可能需要根据自动机状态和转换将输入放置在磁带上，否则您将无法接受。
因此，我们最近在 class 中讨论了线性有界自动机的主题，但我们并没有正式定义它们。网上查了定义，还是搞不清楚marker的定位。它们是否总是应该位于输入字符串的两端？只要它们的距离至多是输入长度的某个常量倍数，它们能否更进一步到 left/right？如果是这样，我们是否可以分别为每个输入字符串选择它们的位置（例如，确保左侧标记始终位于输入字符串之前）？
线性有界自动机是非确定性图灵机的一种受限形式。限制是磁带是有限的。这是通过用 标记 限制磁带两端来确保的。仅此而已。
现在，您如何选择这些标记与自动机无关，因为与左右标记的距离（即磁带的长度）是输入长度的线性函数。
图灵机从一个磁带开始，磁带上“某处”写入了输入，磁带的头部指向它的第一个符号。 LBA 没有对此添加新的限制，因此它仍然存在：输入在某处。这意味着（由于限制标记）输入在两个标记之间 ，您可以将输入的第一个符号放在左侧标记之后，或者将输入的最后一个符号放在右侧标记之前标记。 LBA 的定义并不禁止这两种情况。
自动机如何使用磁带上输入的不同位置及其状态是另一个话题。换句话说，您可能需要根据自动机状态和转换将输入放置在磁带上，否则您将无法接受。