Forma Normal De Greibach

Forma Normal de Greibach
Veremos otra posible normalización de gramáticas que nos sirve más adelante para construir cierto tipo de autómatas.
Una gramática es en forma normal de Greibach (FNG) si* (es decir, su ) solamente contiene variables útiles
* todas las producciones de (es decir, en su ) son de la forma donde y , es decir, todas las reglas tienen como primer símbolo en suspartes derechas un símbolo terminal que es seguido por una palabra de variables.
* (porque así no se podría derivar ) si (es decir, el símbolo inicial de ) no aparece al lado derecho de unaproducción, también está permitido que
Obviamente cualquier gramática en forma normal de Greibach es una gramática libre de contexto que se verifica directamente analizando la forma de produccionespermitidas.
Una interesante propiedad es: para cualquier lenguaje libre de contexto existe una gramática en forma normal de Greibach, que genera el lenguaje.
La comprobación de este hecho detallamos conla siguiente construcción, donde a partir de una gramática libre de contexto dada elaboramos una nueva gramática en forma normal de Greibach.
Sea un lenguaje libre de contexto y una gramática quegenere (es decir ).
La construcción sigue 4 pasos (asumimos que , eso remediamos al final):
1. construimos una gramática equivalente en forma normal de Chomsky
2. sustituimos las reglasrecursivas a la izquierda, es decir, reglas de tipo
3. establecemos un orden en las variables, es decir de tal manera que todas las reglas serán de tipo con ,
4. sustituimos las reglas que notengan un símbolo terminal como primer símbolo en su parte derecha.
Las gramáticas después de cada paso llamamos respectivamente.
Usamos la misma gramática inicial como en el apartado anteriordonde contenga las siguientes producciones:

como ejemplo para realizar todos los pasos.
1. La transformación a FNC hicimos arriba. Entonces ya tenemos como

solo reordenado, para que...