Formas normales de Greibach

Daniela Guadalupe García García
Teoría de la Computación A342
3.4 Formas normales de Greibach

1. Una gramática libre de contexto esta en forma normal de Greibach si:
R= Todas las funcionesson de la forma , donde a es un símbolo terminal y
2. ¿Cuándo una gramática libre de contexto se puede transformar?
R= Cuando no generen palabras bacías se puede trasformar en una gramáticalibre de contexto en forma normal de Greibach.

3.¿ Que es lo que no pude tener una forma normal de Greibach?
R= No puede tener producciones recursivas por la izquierda. Sólo puede generar lenguajesno vacíos que no contengan la e.



4.¿ Que los lo primero que tenemos que ver para transformar?
R= Debemos observar si podemos ``componer producciones'' de manera que tengamos siempre unagramática equivalente a la gramática dada.

5. ¿Que es una composición de producción?
R= Si Si es una producción en G y las producciones en P(Y) pueden escribirse como | entonces al sustituir por lasproducciones , obtenemos una gramática equivalente a G.
En efecto, en toda derivación terminal que aplique en un momento la producción, necesariamente se ha de aplicar una producción en P(Y) parasuprimir el símbolo Y.


6. Sea G'=(V',T,P',S') la forma normal de Chomsky de G.
R= Modificaremos a las producciones en P' para tenerlas tales que toda producción, cuyo consecuente se inicie conuna variable, ha de ser de la forma con j>i, para un cierto orden en el conjunto de variables actuales, digamos . Para esto apliquemos el procedimiento cuyo seudo código se presenta.

Modificación deproducciones de acuerdo con el orden de V'.


7. Después de haber hecho la transformación anterior, se debe de hacer:
R=La última variable Xm sólo puede ser antecedente de producciones cuyosconsecuentes se inician con símbolos terminales, las producciones en P(Xm-1) cuyos consecuentes se inician con Xm pueden transformarse, siguiendo el tema de ``Composición de producciones'', en...