formal-languages - 再帰言語と文脈依存言語

Question

チョムスキーのヒエラルキーでは、再帰言語のセットは定義されていません。再帰言語は再帰的に列挙可能な言語のサブセットであり、すべての再帰言語は決定可能であることを知っています。

私が興味を持っているのは、再帰言語が文脈依存言語とどのように比較されるかということです。文脈依存言語は再帰言語の厳密なサブセットであり、したがってすべての文脈依存言語は決定可能であると仮定できますか?

Answer 1

再帰言語を認識するには、 Deciderという名前の一種のオートマトンが必要です。それはまさに、制限された制御フローによってだまされたチューリング マシンです。つまり、常に停止するようにします。

文脈依存言語に関しては、それらは確かに再帰言語の適切なサブセットです。文脈依存言語を認識するための最小限のオートマトンであるLinear bounded automatonが決定者よりも強力ではないことを考えると、それは些細なことです。文法制限規則に基づいて実証することも可能だと思います。

Answer 2

文脈依存言語のセットは、再帰言語の適切なサブセットです。これを仮定する必要はありません。証明については、Peter Linz の本を参照してください。

Answer 3

あなたの質問が、すべての文脈依存言語がすべての再帰言語のセットに含まれている場合のみである場合は、正式なオートマトンを通じて古典的な方法でそれを証明するようにしてください。文脈依存言語の生成をシミュレートできる形式オートマトンと、再帰言語の生成に使用されるものを自問してください。次に、一方を他方を使用してシミュレートしてみてください。教科書で適切なオートマトンを調べれば、あなたが望むものを確実に証明できるでしょう。

Answer 4

Papadimitriou の本 (3.4.2 (e)) によると、文脈依存文法は、再帰言語の適切なサブセットである NSPACE(n) と同等です。だから、はい、あなたの仮定は正しいです。