言語用のコンテキストフリーグラマーを作成します

Question

私は有限のオートマトンのクラスを受講しています。私は中期の準備をしており、特定の言語の文法を作成するのに苦労しています。単純なものは非常に直感的であると思いますが、それらがより複雑になると、どこから始めればいいのかわかりません。例えば：

l = {w e {a、b、c}*：nb（w）！= na（w） + nc（w）}

答えは次のとおりです。

S→S1 | S2
S1→BS3 | S3B | S3BS3
S3→S0 | S1
S2→XS4 | S4x | S4XS4
S4→S | S2
S0→BS0XS0 | XS0BS0 | e
x→a | c

誰かが私に関係する思考プロセスについて少しガイダンスを与えることができれば、それは大歓迎です。

Answer 1

リストした言語は不明です。私は仮定しています w E {a,b,c}* 意味 w ε {a,b,c}* と nb(w) != na(w) + nc(w) 言語のすべての文字列は、aの数とcの数の合計に等しくない多くのbを持っていることを意味します。

この場合、言語にあるすべての文字列の特性と、この言語にあることから文字列を除外するすべての特性について考える必要があります。

この言語は、bの数が=/= cの数の数を受け入れます。この言語を再定式化することができます。

番号 a's + number c's>数 b'sまたはnumber a's + number c's <of b's

これは、最初のs-> s1 |を説明しますS2

S1は、少なくとも1つあることを保証します b （s3）、そして等しい量のいずれかを強制します b's as a'砂 c's（s0）以上 b's a'砂 c's（s1）。 S1ルールの最終的な結果は、より多くの文字列です b's a'砂 c's。

S2はもっとあることを保証します a'sおよび/または c's b's。これを強制することによってこれを行います a また c （x）、その後、等しい量を許可します a's/c's（s0）以上 a's/c's b's（s2再び）。

これはあなたの例に固有のものですが、この文法を作成することにかかる思考プロセスをどのように見ることができます。

1. 具体的なケースとして言語を策定する（a's/c's> or b's）
2. 各ケースについて、ケースが保持されることを確認することから始めます（フォース＃ b's> than a's/c少なくとも1つを強制することによって b）その後、文字列を拡張して、等しいすべての可能性を含める a's/c'砂 b's以下 a's/c's b's。
3. 他のケースを対称的に処理します。

問題は、言語内のすべての文字列が生成され、言語ではないすべての文字列が生成されないことを確認する必要があることです。 （それが沈むまでこれを読み直します）