context-free-grammar - 非文脈自由言語、それらは何ですか?

Question

文脈自由でない言語を理解するのにかなり苦労しています。簡単に言えば、それらは再帰的に列挙可能ですか? のように、チューリング マシンを使用して非文脈自由言語を表現できますか? チューリングマシンによって認識可能または共同認識可能ですか?

Answer 1

多くの非コンテキストフリー言語は再帰的です。考慮してください(a^n)(b^n)(c^n)。この言語の単純なチューリング マシンは、すべてのシンボルが削除されるか、別の種類のシンボルがなくなるまで、パス内の各シンボルの 1 つを削除しながら、テープを前後に実行できます。再帰言語も再帰的に列挙可能です。

チョムスキー階層は、規則的で、文脈に依存せず、文脈に依存し、(大まかに) 再帰的になります。これを超えるレベルがあり、これらの標準的なレベルの間にあるレベルやまたがるレベルもあります。