formal-languages - 递归语言与上下文相关语言

Question

在乔姆斯基的层次结构中，没有定义递归语言集。我知道递归语言是递归可枚举语言的子集，并且所有递归语言都是可判定的。

我很好奇的是递归语言与上下文相关语言的比较。我可以假设上下文相关语言是递归语言的严格子集，因此所有上下文相关语言都是可判定的吗？

score 1 · Accepted Answer

要识别递归语言，您需要一种名为Decider的自动机。它正是一个被有限控制流欺骗的图灵机，也就是说，它确保它总是会停止。

关于上下文相关语言，它们确实是递归语言的适当子集。识别上下文相关语言的最小自动机是微不足道的，线性有界自动机严格来说不如决策者强大。我想也可以根据语法限制规则进行演示。

score 1 · Accepted Answer

如果您的问题只是每个上下文相关语言都在所有递归语言的集合中，那么您应该尝试通过形式自动机以经典方式证明它。问问自己，什么形式自动机可以模拟上下文相关语言的生成，以及什么用于生成递归语言。然后试着用另一个来模拟一个。一旦你在你的教科书中找到了正确的自动机，你肯定能够证明你想要什么。

score 1 · Accepted Answer

一组上下文敏感语言是递归语言的适当子集。您不必假设这一点，请参阅 Peter Linz 的书以获取证据。

score 0 · Accepted Answer

根据 Papadimitriou 的书 (3.4.2 (e))，上下文相关文法等价于 NSPACE(n)，它是递归语言的真子集。所以，是的，你的假设是正确的。

score 0 · Accepted Answer

根据我的参考资料，我还要说上下文敏感语言是所有递归语言集合的正确子集。您可以在任何标准教科书中找到这个证明，例如

> Peter Linz 的形式语言和自动机介绍（第 5 版）

5 回答 5