次の言語をご覧ください。
(a, b, c)* − {anbncn|n≥0}
私の質問は次のとおりです。文脈自由文法をどのように書くのですか?
一般に、何かが除外されている (つまり、"-" 記号がある) 場合、どうすれば文法を記述できますか?
質問する
465 次
2 に答える
1
言語が文脈自由かどうかを判断するアルゴリズムはありません。したがって、あなたが提起した質問に対する一般的な解決策がないことは驚くべきことではありません.
文脈自由言語は、補完、セットの違い、または交差の下で閉じられません。(ただし、これらは連結、集合結合、および Kleene スターの下では閉じられています。) いずれにせよ、
{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}
于 2016-04-03T21:18:55.460 に答える
0
(a, b, c)* − {a^nb^nc^n|n≥0}
これは、a、b、または c のいずれかを選択して、それらのいずれかを繰り返すことができることを示しています (例: abccbaabaab または abca または bccc)
a* には、A->aA |eor を代わりに使用しますA->AA | a | e。
そのルールを使用すると、次のことができます。
S -> A | B | C
A->aA |e | AS
B->bB |e | BS
C->cC |e | CS
A、B、C のそれぞれに S を含めることは、全体に Kleene スターがある場合に使用できるものであり(....)*、最初に戻って別のシンボルを追加することができます。
記号を除外する文法を作成する方法がわかりませんが、論理的に-は、利用可能な終端記号がない場合は、既に除外されています。
于 2016-05-04T15:50:16.710 に答える