grammar - この言語を生成する文法をどのように構築できますか?

Question

私は有限オートマトンと文法テストのために勉強していますが、この質問に行き詰まっています:

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 の数をどのように記憶できますか? これはむしろ文脈自由文法でなければならないと思います。

score 8 · Accepted Answer

次のようになります。

A->aAc | aBc | ac | epsilon
B->bBc | bc | epsilon

建設プロセス中にC'cを強制的にカウントする必要があります。文脈自由であることを示すために、 PumpLemmaの使用を検討します。

score 4 · Accepted Answer

S -> X
X -> aXc | Y
Y -> bYc | e

e == epsilonとXは不要ですが、わかりやすくするために追加されています

score 2 · Accepted Answer

はい、これは宿題のように聞こえますが、ヒント：

'a'に一致するたびに、'c'に一致する必要があります。'b'のマッチングについても同じです。

score 0 · Accepted Answer

S->aSc|A A->bAc|λ

これは、a を取得するたびに少なくとも 1 つの c を取得するか、a と b を取得する場合は 2 つの c を取得する必要があることを意味します。お役に立てば幸いです

score 0 · Accepted Answer

0

私の答え：

S -> aAc | aSc

A -> 紀元前 | バック

ここで、S は開始記号です。

于 2019-12-07T15:52:45.853 に答える

6 に答える 6