¿Cómo puedo construir una gramática que genere este lenguaje?

Question

Estoy estudiando para un autómata finito & amp; prueba de gramáticas y estoy atascado con esta pregunta:

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

Creo que mis producciones deberían ir en esta línea:

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

¿Cómo puede mi producción para C recordar los números de myn? Supongo que esto debe ser una gramática libre de contexto, si es así, ¿cómo debería ser?

Answer 1

Parece que debería ser así:

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

Debe forzar que C'c se cuente durante el proceso de construcción. Para mostrar que no tiene contexto, consideraría usar Pump Lemma .

Answer 2

Sí, esto suena como tarea, pero una pista:

Cada vez que coincida con una 'a', debe coincidir con una 'c'. Lo mismo para hacer coincidir una 'b'.

Answer 3

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

donde e == epsilon y X es innecesario pero añadido para mayor claridad

Answer 4

S- > aSc | A A- > bAc | ?

Esto significa que cuando obtienes al menos tienes 1 c o si obtienes a y b debes tener 2 c. espero que te haya sido útil

Answer 5

Bueno chicos, así es como lo haré:

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