證明常規語言和上下文無關語言是遞歸的

Question

我對常規語言和上下文無關語言之間的區別有點困惑。遞歸語言是一種語言，爲此它退出一直停止的TM。 我在證明上述說法時遇到問題。

Answer 1

正常語言被有限自動機接受，它沒有可用內存。下推式自動機可接受上下文無關語言，下推式自動機具有單個堆棧（支持push/pop）用於存儲器。遞歸語言是一種可由圖靈機決定的語言，它有一個（可能）無限大的內存磁帶。常規語言是遞歸的，因爲您可以通過不使用磁帶來使TM等同於FA。上下文無關語言是遞歸的，因爲您可以通過使用磁帶作爲堆棧來創建與PDA相當的TP：僅讀取和寫入最後一個非空白符號。這缺乏細節，但可以作爲你要求證明的要求的嚴格證明。