递归语言与上下文相关语言

Question

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

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

Answer 1

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