递归语言与上下文敏感语言

Question

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

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

Answer 1

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

Answer 2

上下文敏感语言集合是递归语言的一个真子集。 你不必假设这一点，请参考Peter Linz的书来证明。

Answer 3

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

关于上下文敏感语言，它们确实是递归的子集。这是微不足道的，因为最小的自动机识别上下文敏感的语言，Linear bounded automaton严格不如决定者强大。我想也可以基于语法限制规则来演示。

Answer 4

根据Papadimitriou的书（3.4.2（e）），上下文敏感的语法相当于NSPACE（n），它是递归语言的一个真子集。所以，是的，你的假设是正确的。