$ \ epsilon $ Productionsが許可されている場合は、状況依存文法となるのでしょうか。

Question

3つの制限文法タイプのChomskyの元の定式化はすべて、置換の右辺を $ \ epsilon $ にすることができない制限を含めました。契約）。ただし、これは通常の文法と文脈のない文法のために（そして通常は）持ち上げることができます（つまり、 $ X \ to \ epsilon $ ）生成された言語のクラスを変更せずに。

ただし、

ルールは文脈依存文法のために残ります。

私の質問は、プロダクションを持つ文法を考えると、 $ \ alpha x \ beta \ to \ alpha \ xi \ beta $ $ \ alpha、\ beta、\ xi \ in（n \ cup t）^ * $ （つまり、 $ \ epsilon $を持つ状況依存文法"スパン> -rules）、それはどのような種類の言語を記述しますか？再帰的に列挙されたもの（無制限の文法と同じ）または他のものは？

Answer 1

あなたが記述する状況依存文法は、 $ \ alpha \ to \ beta $ を $ \ lvert \ alpha \ rvert \ leververt \ beta \ rvert $ 。そのため、プロダクションを許可 $ A \ VAREPSILON $ の制限を削除するだけで、無制限の文法に上陸しました。