文脈自由言語のコレクションの和集合は常に文脈自由ですか？あなたの答えを正当化してください.....
答えがイエスであることは知っていますが、どうすればそれを証明できますか？
質問する
1666 次
1 に答える
1
文脈自由言語の有限和集合が文脈自由であることを示すには、2 つの文脈自由言語の和集合が文脈自由であることを証明する場合とまったく同じように、和集合言語の文脈自由文法を構築する必要があります。 .
G1,...,GN が N 個の文脈自由言語の文脈自由文法である場合、各文法のすべての記号の名前を変更し (記号名の衝突を避けるためだけに添え字を追加します)、新しい文法 G を作成します。 N 文法のすべてのプロダクションに加えて、次のプロダクションを使用します。
S -> S1 | S2 | ... | SN
この文法はユニオン言語を生成し、コンテキストフリーです。
于 2012-05-04T18:28:10.390 に答える