この言語を生成する文法を作成するにはどうすればよいですか?
-
06-07-2019 - |
質問
私は有限オートマトンのために勉強しています&文法テストをして、この質問にこだわっています:
Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}
自分の作品は次のラインに沿って進むべきだと思います:
S->aA | aB
B->bB | bC
C->cC | c Here's where I have doubts
Cのプロダクションでは、mとnの数をどのように記憶できますか?私はこれがむしろ文脈自由文法でなければならないと推測しています、もしそうなら、それはどうあるべきですか?
解決
次のように見えます:
A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon
構築プロセス中にC'cを強制的にカウントする必要があります。コンテキストフリーであることを示すために、 Pump Lemma を使用することを検討します。
他のヒント
はい、これは宿題のように聞こえますが、ヒント:
「a」に一致するたびに、「c」に一致する必要があります。 「b」と一致する場合も同じです。
S -> X
X -> aXc | Y
Y -> bYc | e
where e == epsilon
および X
は不要ですが、
明確にするために追加
S-> aSc | A A-> bAc |λ
これは、少なくとも1つのcを取得する場合、またはaとbを取得する場合は2 cを取得する必要があることを意味します。 お役に立てば幸いです
まあ、これは私がやる方法です:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}
所属していません StackOverflow