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

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

Una gramática libre de contexto (CFG) está en la forma normal de Chomsky (CNF) 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 dos no terminales (p. ej., X->YZ)
• Símbolo de inicio que genera ε. (por ejemplo, S-> ε)

Considere las siguientes gramáticas,

G1 = {S->a, S->AZ, A->a, Z->z} 
G2 = {S->a, S->aZ, Z->a}

La gramática G1 está en CNF ya que las reglas de producción satisfacen las reglas especificadas para CNF. Sin embargo, la gramática G2 no está en CNF ya que la regla de producción S->aZ contiene un terminal seguido de un no terminal que no cumple las reglas especificadas para CNF.

Nota –

• Para una gramática dada, puede haber más de un CNF.
• CNF produce el mismo lenguaje generado por CFG.
• CNF se usa como un paso de preprocesamiento para muchos algoritmos para CFG como CYK (algoritmo de membresía), analizadores de abajo hacia arriba, etc.
• Para generar una string w de longitud ‘n’ se requiere la producción ‘2n-1’ o pasos en CNF.
• Cualquier gramática libre de contexto que no tenga ε en su lenguaje tiene un CNF equivalente.

¿Cómo convertir CFG a CNF?

Paso 1. Eliminar el símbolo de inicio de RHS.
Si el símbolo de inicio S está en el RHS de cualquier producción en la gramática, cree una nueva producción como:
S0->S
donde S0 es el nuevo símbolo de inicio.

Paso 2. Eliminar producciones nulas, unitarias e inútiles.
Si CFG contiene reglas de producción nulas, unitarias o inútiles, elimínelas. Puede consultar este artículo para eliminar este tipo de reglas de producción .

Paso 3. Eliminar terminales de RHS si existen con otros terminales o no terminales. p.ej,; la regla de producción X->xY se puede descomponer como:
X->ZY
Z->x

Paso 4. Eliminar RHS con más de dos no terminales.
p.ej,; la regla de producción X->XYZ se puede descomponer como:
X->PZ
P->XY

Ejemplo: tomemos un ejemplo para convertir CFG a CNF. Considere la gramática dada G1:

S → ASB
A → aAS|a|ε 
B → SbS|A|bb

Paso 1. Cuando aparezca el símbolo de inicio S en el RHS, crearemos una nueva regla de producción S0->S. Por lo tanto, la gramática se convertirá en:

S0->S
S → ASB
A → aAS|a|ε 
B → SbS|A|bb

Paso 2. Como la gramática contiene producción nula A-> ε, su eliminación de la gramática produce:

S0->S
S → ASB|SB
A → aAS|aS|a 
B → SbS| A|ε|bb

Ahora, crea una producción nula B→ ε, su eliminación de la gramática produce:

S0->S
S → AS|ASB| SB| S
A → aAS|aS|a 
B → SbS| A|bb

Ahora, crea la unidad de producción B->A, su eliminación de la gramática produce:

S0->S
S → AS|ASB| SB| S
A → aAS|aS|a 
B → SbS|bb|aAS|aS|a

Además, la eliminación de la producción unitaria S0->S de la gramática produce:

S0-> AS|ASB| SB| S
S → AS|ASB| SB| S
A → aAS|aS|a 
B → SbS|bb|aAS|aS|a

Además, la eliminación de la producción unitaria S->S y S0->S de la gramática produce:

S0-> AS|ASB| SB
S → AS|ASB| SB
A → aAS|aS|a 
B → SbS|bb|aAS|aS|a

Paso 3. En la regla de producción A->aAS |aS y B-> SbS|aAS|aS, las terminales a y b existen en RHS sin terminaciones. Eliminarlos de RHS:

S0-> AS|ASB| SB
S → AS|ASB| SB
A → XAS|XS|a
B → SYS|bb|XAS|XS|a
X →a
Y→b

Además, B->bb no puede ser parte de CNF, al eliminarlo de la gramática se obtiene:

S0-> AS|ASB| SB
S → AS|ASB| SB
A → XAS|XS|a
B → SYS|VV|XAS|XS|a
X → a
Y → b
V → b

Paso 4: en la regla de producción S0->ASB, RHS tiene más de dos símbolos, al eliminarlo de la gramática se obtiene:

S0-> AS|PB| SB
S → AS|ASB| SB
A → XAS|XS|a
B → SYS|VV|XAS|XS|a
X → a
Y → b
V → b
P → AS

De manera similar, S->ASB tiene más de dos símbolos, al eliminarlo de la gramática se obtiene:

S0-> AS|PB| SB
S → AS|QB| SB
A → XAS|XS|a
B → SYS|VV|XAS|XS|a
X → a
Y → b
V → b
P → AS
Q → AS

De manera similar, A->XAS tiene más de dos símbolos, al eliminarlo de la gramática se obtiene:

S0-> AS|PB| SB
S → AS|QB| SB
A → RS|XS|a
B → SYS|VV|XAS|XS|a
X → a
Y → b
V → b
P → AS
Q → AS
R → XA

De manera similar, B->SYS tiene más de dos símbolos, al eliminarlo de la gramática se obtiene:

S0 -> AS|PB| SB
S → AS|QB| SB
A → RS|XS|a
B → TS|VV|XAS|XS|a
X → a
Y → b
V → b
P → AS
Q → AS
R → XA
T → SY

De manera similar, B->XAX tiene más de dos símbolos, al eliminarlo de la gramática se obtiene:

S0-> AS|PB| SB
S → AS|QB| SB
A → RS|XS|a
B → TS|VV|US|XS|a
X → a
Y → b
V → b
P → AS
Q → AS
R → XA
T → SY
U → XA

Entonces este es el CNF requerido para una gramática dada.