Forma normal de Greibach

Un CFG está en la forma normal de Greibach si las producciones están en las siguientes formas:

A → b

A → bD ₁ … D _n

S → ε

donde A, D ₁ , ...., D _n no son terminales y b es un terminal.

Algoritmo para convertir un CFG en forma normal de Greibach

Step 1 - Si el símbolo de inicio S ocurre en algún lado derecho, crea un nuevo símbolo de inicio S’ y una nueva producción S’ → S.

Step 2- Eliminar producciones nulas. (Usando el algoritmo de eliminación de producción nula que se discutió anteriormente)

Step 3- Eliminar producciones unitarias. (Usando el algoritmo de eliminación de producción de unidades discutido anteriormente)

Step 4 - Eliminar todas las recursiones por la izquierda directas e indirectas.

Step 5 - Hacer sustituciones adecuadas de producciones para convertirlo en la forma adecuada de GNF.

Problema

Convierta el siguiente CFG en CNF

S → XY | Xn | pag

X → mX | metro

Y → Xn | o

Solución

Aquí, Sno aparece en el lado derecho de ninguna producción y no hay producciones unitarias o nulas en el conjunto de reglas de producción. Entonces, podemos saltarnos del Paso 1 al Paso 3.

Step 4

Ahora, después de reemplazar

X en S → XY | Xo | pag

con

mX | metro

obtenemos

S → mXY | mY | mXo | mo | pag.

Y después de reemplazar

X en Y → X _n | o

con el lado derecho de

X → mX | metro

obtenemos

Y → mXn | mn | o.

Se agregan dos nuevas producciones O → o y P → p al conjunto de producción y luego llegamos al GNF final de la siguiente manera:

S → mXY | mY | mXC | mC | pag

X → mX | metro

Y → mXD | mD | o

O → o

P → p