grammar - 具有非确定性图灵机的上下文敏感语言

Question

如何使用非确定性图灵机显示语言对上下文敏感？

我知道线性绑定自动机（LBA）接受的语言是上下文相关的语言。LBA 是一个非确定性的图灵机。

知道如何将所有这些联系起来并表明一种语言是上下文相关的吗？

Answer 1

由于 templatetypedef 的回答有一些缺陷（我将在评论中指出），我快速回答你的问题：

当（且仅当）您可以使用定义 L 的线性空间给出非确定性图灵机时，该语言是上下文相关的。

令 L = { a^nb^na^n } 为任意整数 n；a^n 在这里表示符号 a 的 n 个串联。这是一种典型的上下文敏感语言。您可以提供 LBA 来表明 L 是上下文相关的，而不是提供 CSG：

图灵机 M '猜测'（由于非确定性）n [换句话说，你可以说'非确定性搜索树的每个分支都尝试另一个 n]，然后检查输入是否匹配 a^nb^na^n。您需要 log n 个单元格来存储 n，匹配可能需要（如果简单地实现）另一个 log n 个单元格。由于 n + 2log n < 2n，这台机器只需要线性空间，因此是 LBA，因此 L 是上下文敏感的。

Answer 2

This is not an exact answer, but since the context-sensitive languages are precisely those accepted by a linear-bounded automaton (a TM with O(n) space on its tape), the context-sensitive languages are precisely those in DSPACE(n). Moreover, we know that NTIME(n) = DSPACE(n). This means that if you can find a linear-time NTM that decides membership in some language L, that language must be context-sensitive. However, there still might be a context-sensitive language that does not have a linear-time NTM (I don't know whether there is a definitive answer to this or whether this is an open problem), so this is not an exact characterization.

Hope this helps!