Forma normal de Chomsky

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

  • A → a
  • A → BC
  • S → ε

donde A, B y C son no terminales y a es terminal.

Algoritmo para convertir en forma normal de Chomsky -

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 - Reemplazar cada producción A → B1…Bn dónde n > 2 con A → B1C dónde C → B2 …Bn. Repita este paso para todas las producciones que tengan dos o más símbolos en el lado derecho.

Step 5 - Si el lado derecho de alguna producción está en el formulario A → aB donde a es una terminal y A, B son no terminales, entonces la producción se reemplaza por A → XB y X → a. Repita este paso para cada producción que tenga el formularioA → aB.

Problema

Convierta el siguiente CFG en CNF

S → ASA | aB, A → B | S, B → b | ε

Solución

(1) Ya que S aparece en RHS, agregamos un nuevo estado S0 y S0→S se agrega al conjunto de producción y se convierte en -

S 0 → S, S → ASA | aB, A → B | S, B → b | ∈

(2) Ahora eliminaremos las producciones nulas -

B → ∈ y A → ∈

Después de eliminar B → ε, el conjunto de producción se convierte en -

S 0 → S, S → ASA | aB | a, A → B | S | ∈, B → b

Después de eliminar A → ∈, el conjunto de producción se convierte en -

S 0 → S, S → ASA | aB | a | AS | SA | S, A → B | S, B → b

(3) Ahora eliminaremos las producciones unitarias.

Después de eliminar S → S, el conjunto de producción se convierte en -

S 0 → S, S → ASA | aB | a | AS | SA, A → B | S, B → b

Después de eliminar S 0 → S, el conjunto de producción se convierte en -

S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → B | S, B → b

Después de eliminar A → B, el conjunto de producción se convierte en -

S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → S | segundo

B → b

Después de eliminar A → S, el conjunto de producción se convierte en -

S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → b | ASA | aB | a | AS | SA, B → b

(4) Ahora encontraremos más de dos variables en el RHS

Aquí, S 0 → ASA, S → ASA, A → ASA viola dos no terminales en RHS

Por lo tanto, aplicaremos el paso 4 y el paso 5 para obtener el siguiente conjunto de producción final que está en CNF:

S 0 → AX | aB | a | AS | SA

S → AX | aB | a | AS | SA

A → b | AX | aB | a | AS | SA

B → b

X → SA

(5)Tenemos que cambiar las producciones S 0 → aB, S → aB, A → aB

Y el conjunto de producción final se convierte en ...

S 0 → AX | YB | a | AS | SA

S → AX | YB | a | AS | SA

A → b A → b | AX | YB | a | AS | SA

B → b

X → SA

Y → a