通常の言語と文脈自由な言語が再帰的であることを証明してください。

Question

私は、通常と文脈自由言語の違いとちょっと混同しています。 再帰言語は、常に停止するTMが存在する言語です。 私は上記の声明を証明する際に問題に直面しています。

Answer 1

通常の言語は、使用可能なメモリがない有限オートマトンによって受け入れられます。コンテキストフリーの言語はプッシュダウンオートマトンによって受け入れられます。プッシュダウンオートマトンはメモリ用の単一スタック（プッシュ/ポップをサポート）を持っています。再帰的言語はチューリングマシンによって決定されるもので、メモリのために（潜在的に）無限のテープがあります。通常の言語は、テープを使用しないことでFAと同等のTMを作成できるため、再帰的です。コンテキストフリーの言語は再帰的です。これは、テープをスタックとして使用することで、PDAと同等のTPを作成できるためです。最後の非空白のシンボルの読み取りと書き込みのみです。これには詳細はありませんが、あなたが証明することを求めているクレームを厳密に証明することができます。