Comment puis-je construire une grammaire qui génère ce langage?

Question

J'étudie pour un automate fini & amp; grammaires test et je suis coincé avec cette question:

Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}

Je pense que mes productions devraient aller dans ce sens:

    S->aA | aB
    B->bB | bC
    C->cC | c Here's where I have doubts

Comment ma production pour C peut-elle mémoriser le nombre de m et de n? Je suppose que cela doit plutôt être une grammaire sans contexte, si oui, comment devrait-elle être?

Answer 1

On dirait que cela devrait être comme:

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

Vous devez obliger C'c à compter pendant le processus de construction. Afin de montrer qu'il est sans contexte, je considérerais d'utiliser Lemme de pompe .

Answer 2

Oui, cela ressemble à un devoir mais un indice:

Chaque fois que vous faites correspondre un "a", vous devez faire correspondre un "c". Pareil pour faire correspondre un 'b'.

Answer 3

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

où e == epsilon et X sont inutiles mais ajouté pour plus de clarté

Answer 4

S- > aSc | A A- > bAc | & # 955;

Cela signifie que chaque fois que vous obtenez a, vous avez au moins 1 c ou si vous obtenez a et b, vous devez en avoir 2 c. J'espère que cela a été utile

Answer 5

Eh bien les gars, voici comment je vais le faire:

P={S::=X|epsilon,
   X::=aXc|M|epsilon,
   M::=bMc|epsilon}