0

それは、非決定論的な文脈自由言語だけがユニオンの下で閉じられているということですか? では、ほとんどすべての教科書やサイトで、CFL は一般にユニオンの下で閉鎖されていると言及されているのはなぜですか? 直感的な説明で十分です。詳細な証明は必要ありません。

4

1 に答える 1

1

決定論的プッシュダウン オートマトンによって認識できる言語として定義される決定論的コンテキスト フリー言語(DCFL) は、CFL の適切なサブセットです (さらに、DFCL は明確な文法を持つ CFL の適切なサブセットです)。言い換えれば、すべての DCFL は明確な文脈自由文法を認めています。

これは、2 つの DFCL の結合が DFCL である必要がないことを意味します。私の直感では、決定論的プッシュダウン オートマトンは、2 つの DFCL の結合に直面すると、別の状態遷移を選択できなくなります。つまり、2 つの DCFL は明確な文法を認めますが、それらの和集合は必ずしもそうである必要はありません。

CFL は、大まかに言えば、文脈自由言語 L が与えられた場合、L の文字列の各記号を文脈自由言語全体で置き換えることができるという、置換定理と呼ばれる強力な結果から導かれる和集合の下で閉じられます。文脈自由言語になってしまいます。( John Hopcroft、Jeff Ullman、故 Rajeev Motwani による言語、オートマトン、および計算の理論の紹介の第 7 章を​​参照してください。)

于 2016-04-05T09:17:51.427 に答える