3

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

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

答えは次のとおりです。

S→S1| S2S1
→bS3| S3b | S3bS3S3
→S0| S1S2
→XS4| S4X | S4XS4S4
→S| S2S0
→bS0XS0| XS0bS0 | eX→ a
| c

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

4

1 に答える 1

3

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

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

この言語は、bの数= /=aの数+cの数である文字列を受け入れます。この言語を、次のような文字列を受け入れる言語に再定式化できます。

数a's+数c's>数b'sOR数a's+数c's<数b's

これは最初のS->S1|を説明します S2

S1は、少なくとも1つb（S3）あることを確認してから、同じ量の'sと's（S0）、または'sと's（S1）よりも多い'sのいずれbかaをc強制しbます。S1ルールの最終的な結果は、'sおよび' sよりも多くの'sを持つ文字列です。 acbac

S2は、'sよりもa'sおよび/または'sが多いことを確認します。これは、または（X）を強制し、次に's / 's（S0）または's（S2）よりも多い' s/ 'sを許可することによって行われます。cbacacacb

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

  1. 言語を具体的なケースとして定式化する（a's / c's>または< b's）
  2. それぞれの場合について、ケースが保持されることを確認することから始め（少なくとも1つを強制することにより、 ＃ b's>をa's / 'sよりも強制します）、文字列を拡張して、's/ 'sと'sが等しいすべての可能性を含めます、または's/ 'sより's未満。 cbacbacb
  3. 他のケースを対称的に処理します。

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

于 2010-11-16T19:00:45.660 に答える