¿Cómo puedo construir una gramática que genere este lenguaje?
-
06-07-2019 - |
Pregunta
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?
Solución
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 .
Otros consejos
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'.
S -> X
X -> aXc | Y
Y -> bYc | e
donde e == epsilon
y X
es innecesario pero
añadido para mayor claridad
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
Bueno chicos, así es como lo haré:
P={S::=X|epsilon,
X::=aXc|M|epsilon,
M::=bMc|epsilon}