recursion - 证明常规语言和上下文无关语言是递归的

Question

我对常规语言和上下文无关语言之间的区别有点困惑。递归语言是一种语言，其中存在一个总是停止的 TM。我在证明上述陈述时遇到了问题。

Answer 1

常规语言被有限自动机接受，它们没有可用的内存。下推自动机接受上下文无关语言，它有一个用于内存的堆栈（支持推送/弹出）。递归语言是一种可以由图灵机决定的语言，图灵机具有（可能）无限的内存磁带。常规语言是递归的，因为您可以通过不使用磁带使 TM 等同于 FA。上下文无关语言是递归的，因为您可以通过将磁带用作堆栈来使 TP 等效于 PDA：仅读取和写入最后一个非空白符号。这缺乏细节，但可以作为您要求证明的主张的严格证明。