遞歸語言與上下文敏感語言

Question

在喬姆斯基的層次結構中，沒有定義遞歸語言的集合。我知道遞歸語言是遞歸可枚舉語言的子集，所有遞歸語言都是可確定的。

我很好奇的是遞歸語言與上下文敏感語言的比較。我能否假設上下文敏感語言是遞歸語言的嚴格子集，因此所有上下文敏感語言都是可判定的？

Answer 1

如果你的問題只是在每個上下文敏感語言都在所有遞歸語言的集合中，那麼你應該嘗試通過形式自動機來證明它是經典的方式。問自己什麼形式的自動機可以模擬上下文敏感語言的生成以及用於生成遞歸語言的內容。然後試着用另一個模擬一個。一旦你在教科書中查找正確的自動機，你一定能證明你想要的東西。

Answer 2

上下文敏感語言集合是遞歸語言的一個真子集。 你不必假設這一點，請參考Peter Linz的書來證明。

Answer 3

要識別遞歸語言，您需要一種名爲Decider的自動機。它正是一個受限制的控制流程欺騙的圖靈機，也就是確保它始終停止。

關於上下文敏感語言，它們確實是遞歸的子集。這是微不足道的，因爲最小的自動機識別上下文敏感的語言，Linear bounded automaton嚴格不如決定者強大。我想也可以基於語法限制規則來演示。

Answer 4

根據Papadimitriou的書（3.4.2（e）），上下文敏感的語法相當於NSPACE（n），它是遞歸語言的一個真子集。所以，是的，你的假設是正確的。