Buenas, en este ejercicio la letra es:
Sea L2 = { x#y / x,y ∈{0,1}*, |y|=|x|^2, (la cantidad de 0's en x) mod 2=0, |x| >= 0}
b) Construya una gramática que genere L2
Tratando de entender L2 pienso que son las tiras donde y tiene el doble del largo que x. Luego si en x existen 0's entonces deben ser una cantidad par.
Si mi interpretación es incorrecto me corrigen.
Luego viendo la solución planteada en:
https://www.fing.edu.uy/inco/cursos/teoleng/examenes/ST-Febrero2018.pdf
Trato derivar la tira 100#101001 y al hacerlo termino generando la tira 100#000101001 que a mi entender no pertenece al lenguaje.
Entiendo que tal vez hubo una confusión y se hizo la gramática para que el largo de y sea el cuadrado de x. Pero me parece que con esa idea el autómata de la parte a no se podría hacer o seria muy difícil de lograrlo (al menos para mi).
Los pasos que seguí fueron:
S => R# => YYR00# => YYY100# => YY1YT00# (misma regla 2 veces)=> 1YTYTYT00# => 1YTYTY00T#
=> 1YTYT0YT0#1 => 1YTY0TY0#01 => 1YT0YTT0YT#01 => 1Y0TYT0TY#001 => 10YTTY0TT#001
=> 10YTTY0#01001 => 10YTT0YT#01001 => 10Y0TTY#101001 => 10Y0TT#101001 => 100YTTT#101001
=> 100#000101001
Gracias!