Buenos días.
Haciendo el ejercicio sobre este Lenguaje R.E., usé una forma distinta de generar las tiras. Está claro que soluciones posibles hay varias, pero puntualmente quería consultar sobre si el razonamiento que hice es válido (hay un paso que me genera dudas).
El lenguaje propuesto es el siguiente:
Como primer observación, las "c" se generan a partir de "a" y "b", así que sólo se incluirán reglas para producir estas últimas.
Luego, está el problema de que las "c" que se quieren generar, necesitan estar sobre la derecha, y si no se tiene cuidado al pensar las reglas, se puede conducir a obtener terminales con "b" y "c" mezcladas. Es por esto que pensé en una marca "F provisoria", a la cual le llamé "P". Esta marca "deja pasar" solo las "c" y, luego, se la cambia por una "F", para dejar pasar a las "b."
Ese último paso es el que me genera dudas. Me parece que el razonamiento está bien, dado que intuitivamente funciona (y probando distintas tiras, también). Pero lo que me hace dudar es: esa regla que cambia "P" por "F" es "irreversible". O sea, si la máquina que corre esto, cambió "P" por "F" teniendo aún "c terminales" por generar, entonces le van a quedar "atrapadas" C variables que no va a poder computar.
Las reglas de producción que pensé fueron estas:
# ================================================================================= #
S → I BA P //Variable inicial que inicializa con una marca de Inicio, variables para insertar primero b y luego a, y por último la marca P
B → Bβ | β
A → Aα | α
βα → αβC //Cada vez que una β se encuentra con una α, avanza a la derecha y genera una C.
Cβ → βC // Las C avanzan libremente hacia la derecha
Cα → αC // IDEM
CP → Pc // La C variable "sale" del área de marcas y se convierte en una c terminal.
CP → Fc // Cuando se considera que no hay más C variables para computar, se desaparece la P y aparece F.
βF → Fb // Una vez que apareció F, cada β variable podrá dar paso a una "b" terminal.
Iα → aI // Las "α" variables que ya están la marca inicial, es porque ya sirvieron de multiplicador (no tienen más β con los que "chocarse") , así que pueden ser usadas para generar una "a" terminal
IF → ε // Cuando se termina de computar todo, las marcas desaparecen.
# ================================================================================= #
Bajándolo un poco a tierra mi pensamiento fue: "Necesito una puerta que me deje pasar primero solamente Cs y luego, otra que me deje pasar solamente Bs". Por eso, incluí una regla que cambia "la puerta de Cs" por "la puerta de Bs".
Tengo claro que mientras la gramática no genere tiras inválidas y genere las tiras válidas, está bien. Pero claramente mis reglas necesitan de algún orden de ejecución, porque una vez que esa "puerta de Cs" desaparece, ya no se puede volver a generar. ¿Eso es algo incorrecto? Una cosa es exigir orden en las reglas para no generar tiras inválidas, lo que está mal. Pero ¿está mal exigir orden para que la máquina que lo computa no quede trancada con variables sin poder procesar? (toda tira que tenga variables sin procesar es una tira inválida).
Pido disculpas anticipadas por lo entreverado de mi consulta, pero se me vino esa duda de repente con respecto a "asumir que las reglas se ejecutan de forma prudente para no quedarse trancado".
Gracias de antemano,
Saludos
Santiago