En esta parte se pide una Gramática G1para el lenguaje
L1 = {x#y / x, y en L(1(0|1)*) representan números en binario con |x|=|y|, x <y}
Encontré como solución:
G1 :({S, A, B}, {0,1}, S, P1)
con P1:
S --> 1B
B --> 0B0 | 1B1 | 0A1
A --> 0A0 | 1A1 | 0A1 | 1A0 | #1
que es una Gramática libre de contexto, lo cual implica que el L1 es libre de contexto.
El problema es que la solución del examen demuestra que L1 es recursivamente enumerable, y no veo cual es el error en la gramática de mi solución :(
Gracias,
Silvana