grammar - 状況依存言語の補題をポンピングしますか？

Question

私は文脈依存の補題をポンピングすることをグーグルで調べました、そしてそれは文脈自由言語の結果だけを生み出すようです。

補題をポンピングすることは、言語が文脈自由のみであることを証明することだけを可能にしますか？コンテキストに依存しませんか？

どのようにアイデアはありますか？

Answer 1

ツリー隣接言語に対する「ポンピング補題のような」アプローチは、実際には文献のいたるところで「ツリー隣接言語のポンピング補題」と呼ばれています。これにより、ある言語がツリーに隣接しておらず、したがって、軽度の文脈依存ではないことを証明できます。たぶんこれはあなたが念頭に置いていたものですか？

それは Vijay-Shanker によって彼の博士論文で定義されましたが、残念ながらオンラインでは入手できません。それにもかかわらず、Web を検索すると、その仕組みを簡単に見つけることができます。テュービンゲン大学のこのコースなど、多くのコースが優れた説明を提供しています。

Answer 2

ポンピング補題は2 つあります。正規言語の Lemma をポンピングすることで、言語が正規ではないことを証明できます。文脈自由言語の Lemma をポンピングすることで、言語が文脈自由言語ではなく、したがって規則的ではないことを証明できます。

その他のポンピング補題はありません。言語が文脈依存であることを証明するには、最初に Pumping Lemma を使用して、文脈自由でないことを証明します。次に、特定の言語を実際に生成する文脈依存文法を提供する必要があります。