オートマトン：以下の言語

Question

ためのCFGが言語を以下でご覧下さい：

(a, b, c)* − {anbncn|n≥0}

私の質問です：私はそれのための文脈自由文法を書くにはどうすればよいですか？

一般に、何かが除外されている（「 - 」記号がある）ときに、どのように文法を書くことができますか？

Answer 1

言語にコンテキストがないかどうかを判断するアルゴリズムはありません。だから、疑問に対する一般的な解決策がないことは驚くべきことではありません。

文脈自由な言語は、補完、差異または交差の設定の下で閉じられません。 （しかし、彼らは連結の下で閉じている、労働組合を設定し、クリーネ閉包。）いずれにしても

{anbncn|n≥0}

文脈自由言語ではなく、（あなたの質問のように）その補数は文脈自由です。補完のための文脈自由文法を構築することによるこの事実の証明は、補完下のCFGの非閉鎖のための標準的な例である。アウトラインで

、あなたの言語Lがの労働組合から構成することができます。すべての文字列は、文字が順番になっていないアルファベット{a,b,c}上

• 。つまり、サブ文字列ba、cbまたはcaを含むすべての文字列です。

• {aibjck|i,j,k≥0∧i≠j}

• {aibjck|i,j,k≥0∧j≠k}

Answer 2

(a, b, c)* − {a^nb^nc^n|n≥0}

これは、BまたはCのいずれかを選択し、それらのいずれかが、例えば繰り返し持つことができると言いますabccbaabaabまたはabcaまたはbccc

*の場合は、A->aA |e、あるいはA->AA | a | eを使用します。そのルールを使用して

、あなたがすることができる：A、BおよびCのそれぞれにおけるSの

S -> A | B | C A->aA |e | AS B->bB |e | BS C->cC |e | CS

含めると、全体のことがそれにクリーネ閉包を持っている場合に使用することができるものである(....)*開始点に戻り、別のシンボルを追加することができます。

シンボルが除外されている文法の作成方法はわかりませんが、論理的には-が使用可能なターミナルシンボルでない場合は、既に除外しています。