Conversión de la gramática libre de contexto a la forma normal de Greibach

Requisito previo: gramáticas libres de contexto , simplificación de gramáticas libres de contexto

Una gramática libre de contexto (CGF) está en forma normal de Greibach (GNF) si todas las reglas de producción satisfacen una de las siguientes condiciones:

• Un no-terminal que genera un terminal (p. ej., X->x)
• Un no terminal que genera un terminal seguido de cualquier número de no terminales (p. ej., X->xX1X2…Xn)
• Símbolo de inicio que genera ε. (por ejemplo, S-> ε)

Considere las siguientes gramáticas:

G1 = {S->aA|bB, B->bB|b, A->aA|a} 
G2 = {S->aA|bB, B->bB|ε, A->aA|ε}

La gramática G1 está en GNF ya que las reglas de producción satisfacen las reglas especificadas para GNF. Sin embargo, la gramática G2 no está en GNF ya que las reglas de producción B-> ε y A-> ε no satisfacen las reglas especificadas para GNF (solo el símbolo de inicio puede generar ε).
Nota –

• Para una gramática dada, puede haber más de un GNF
• GNF produce el mismo lenguaje generado por CFG

Cómo convertir CFG a GNF –

Paso 1. Convierte la gramática en CNF.
Si la gramática dada no está en CNF, conviértala a CNF. Puede consultar el siguiente artículo para convertir CFG a CNF: Conversión de la gramática libre de contexto a la forma normal de Chomsky

Paso 2. Eliminar la recursividad por la izquierda de la gramática, si existe.
Si CFG contiene recursividad por la izquierda, elimínelos. Puede consultar el siguiente artículo para eliminar la recursividad izquierda: Análisis | Conjunto 1 (Introducción, Ambigüedad y Analizadores)

Paso 3. Convierta las reglas de producción en formato GNF.
Si alguna regla de producción no está en formato GNF, conviértala. Tomemos un ejemplo para convertir CFG a GNF. Considere la gramática dada G1:

S → XA|BB 
B → b|SB 
X → b 
A → a

Como G1 ya está en CNF y no queda recursividad, podemos omitir los pasos 1 y 2 y pasar directamente al paso 3.
La regla de producción B->SB no está en GNF, por lo tanto, sustituimos S -> XA|BB en producción regla B->SB como:

S → XA|BB 
B → b|XAB|BBB 
X → b 
A → a

Las reglas de producción S->XA y B->XAB no están en GNF, por lo tanto, sustituimos X->b en las reglas de producción S->XA y B->XAB como:

S → bA|BB 
B → b|bAB|BBB 
X → b 
A → a

Eliminando la recursividad por la izquierda (B->BBB), obtenemos:

S → bA|BB 
B → bC|bABC
C → BBC| ε
X → b 
A → a

Eliminando la producción nula (C-> ε), obtenemos:

S → bA|BB 
B → bC|bABC|b|bAB
C → BBC|BB
X → b 
A → a

Las reglas de producción S->BB no están en GNF, por lo tanto, sustituimos B → bC|bABC|b|bAB en las reglas de producción S->BB como:

S → bA| bCB|bABCB|bB|bABB 
B → bC|bABC|b|bAB
C → BBC|BB
X → b 
A → a

Las reglas de producción C->BB no están en GNF, por lo tanto, sustituimos B → bC|bABC|b|bAB en las reglas de producción C->BB como:

S → bA| bCB|bABCB|bB|bABB 
B → bC|bABC|b|bAB
C → BBC
C → bCB|bABCB|bB|bABB
X → b 
A → a

Las reglas de producción C->BBC no están en GNF, por lo tanto, sustituimos B → bC|bABC|b|bAB en las reglas de producción C->BBC como:

S → bA| bCB|bABCB|bB|bABB 
B → bC|bABC|b|bAB
C → bCBC|bABCBC|bBC|bABBC
C → bCB|bABCB|bB|bABB
X → b 
A → a

Esta es la forma GNF para la gramática G1.