具有非确定性图灵机的上下文相关语言
我怎样才能证明一种语言对于非确定性图灵机是上下文敏感的？
我知道线性界限自动机（LBA）接受的语言是上下文相关的语言。 LBA 是一种非确定性图灵机。
知道如何将所有这些联系起来并表明语言是上下文敏感的吗？
how can i show a language is context sensitive with a non deterministic turing machine?
i know that a language that is accepted by a Linear bound automaton (LBA ) is a context -sensitive language. And a LBA is a non-deterministic turing machine.
Any idea how can i relate all these and show that a language is context sensitive?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
由于 templatetypedef 的答案有一些缺陷（我将在评论中指出），我对你的问题给出一个快速答案：
如果（且仅当）你可以使用线性空间给出一个非确定性图灵机，该语言是上下文敏感的定义 L。
令 L = { a^nb^na^n } 对于任意整数 n； a^n 这里表示符号 a 的 n 个串联。这是典型的上下文相关语言。您可以提供 LBA，而不是给出 CSG，以表明 L 是上下文相关的：
图灵机 M '猜测'（感谢非确定性）n [换句话说，您可能会说'非确定性搜索树的每个分支都会尝试另一个分支n]，然后检查输入是否匹配 a^nb^na^n。您需要 log n 个单元来存储 n，匹配可能需要（如果实现简单）另一个 log n 个单元。当 n + 2log n < 2n，这台机器只需要线性空间，因此是一个LBA，因此L是上下文敏感的。
As templatetypedef's answer has some flaws (which I will point out in a second in a comment), I give a quick answer to your question:
The language is context sensitive if (and only if) you can give a nondeterministic turing machine using linear space that defines L.
Let L = { a^n b^n a^n } for an arbitrary integer n; a^n here means n concatenations of the symbol a. This is a typical context sensitive language. Instead of giving a CSG, you can give a LBA to show that L is context sensitive:
The turing machine M 'guesses' (thanks to nondeterminism) n [in other words you may say 'every branch of the nondeterministic search tree tries out another n], and then checks whether the input matches a^n b^n a^n. You need log n cells to store n, the matching might need (if implemented trivially) another log n cells. As n + 2log n < 2n, this machine needs only linear space, and is therefore an LBA, hence L is context sensitive.
这不是一个确切的答案，但由于上下文相关的语言正是线性有界自动机（磁带上具有 O(n) 空间的 TM）所接受的语言，因此上下文相关的语言正是 DSPACE(n) 中的语言）。此外，我们知道NTIME(n) = DSPACE(n)。这意味着如果你能找到一个线性时间 NTM 来决定某种语言 L 中的成员资格，那么该语言必须是上下文相关的。然而，仍然可能存在一种没有线性时间 NTM 的上下文相关语言（我不知道是否有明确的答案，或者这是否是一个开放问题），所以这不是一个确切的表征。
希望这有帮助！
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!