Forma normal de Chomsky

Introducir un nuevo símbolo de inicio S ₀ , y una nueva regla

S ₀ → S ,

donde S es el símbolo de inicio anterior. Esto no cambia el lenguaje producido por la gramática, y S ₀ no aparecerá en el lado derecho de ninguna regla.

Para eliminar cada regla

A → X ₁ ... a ... X _n

con un símbolo terminal a que no es el único símbolo en el lado derecho, introduzca, para cada uno de dichos terminales, un nuevo símbolo no terminal N _a , y una nueva regla

N _a → a .

Cambia todas las reglas

A → X ₁ ... a ... X _n

a

A → X ₁ ... N _a ... X _n .

Si aparecen varios símbolos terminales en el lado derecho, reemplácelos simultáneamente por su símbolo no terminal asociado. Esto no altera el lenguaje producido por la gramática. ^{[ 4 ] : 92}

Reemplazar cada regla

A → X ₁ X ₂ ... X _n

con más de 2 no terminales X ₁ ,..., X _n según las reglas

A → X ₁ A ₁ ,

A ₁ → X ₂ A ₂ ,

...,

A _{n -2} → X _{n -1} X _n ,

donde A _i son nuevos símbolos no terminales. Nuevamente, esto no cambia el lenguaje producido por la gramática. ^{[ 4 ] : 93}

Una regla ε es una regla de la forma

A → ε,

donde A no es S ₀ , el símbolo de inicio de la gramática.

Para eliminar todas las reglas de esta forma, primero determine el conjunto de todos los no terminales que derivan ε. Hopcroft y Ullman (1979) llaman a dichos no terminales anulables y los calculan de la siguiente manera:

• Si existe una regla A → ε, entonces A es anulable.
• Si existe una regla A → X ₁ ... X _n , y cada X _i es anulable, entonces A también es anulable.

Obtén una gramática intermedia reemplazando cada regla.

A → X ₁ ... X _n

por todas las versiones con algún X _i anulable omitido. Al eliminar en esta gramática cada regla ε, a menos que su lado izquierdo sea el símbolo inicial, se obtiene la gramática transformada. ^{[ 4 ] : 90}

Por ejemplo, en la siguiente gramática, con símbolo inicial S ₀ ,

S ₀ → AbB | C

B → AA | AC

C → b | c

A → a | ε

El no terminal A , y por lo tanto también B , es anulable, mientras que ni C ni S ₀ lo son. Por lo tanto, se obtiene la siguiente gramática intermedia: ^{[ nota 3 ]}

S ₀ → A b B | A b B | A b B | A b B | C  

B → AA | A A | A A | A ε A | A C | A C  

C → b | c

A → a | ε

En esta gramática, todas las reglas ε se han " insertado en línea en el sitio de llamada". ^{[ nota 4 ]} En el siguiente paso, se pueden eliminar, lo que da como resultado la siguiente gramática:

S ₀ → AbB | Ab | bB | b  | C 

B → AA | A  | AC | C 

C → b | c

A → a

Esta gramática produce el mismo lenguaje que la gramática de ejemplo original, a saber. { ab , aba , abaa , abab , abac , abb , abc , b , ba , baa , bab , bac , bb , bc , c }, pero no tiene reglas ε.

Una regla de unidad es una regla de la forma

A → B ,

donde A y B son símbolos no terminales. Para eliminarlo, para cada regla

B → X ₁ ... X _n ,

donde X ₁ ... X _n es una cadena de no terminales y terminales, agregar regla

A → X ₁ ... X _n

a menos que se trate de una regla de unidad que ya se haya eliminado (o se esté eliminando). La omisión del símbolo no terminal B en la gramática resultante es posible debido a que B es un miembro del cierre de unidad del símbolo no ^terminal A. ^{[ 9} ]

Al elegir el orden en que se aplicarán las transformaciones anteriores, es necesario considerar que algunas transformaciones pueden anular el resultado obtenido por otras. Por ejemplo, START reintroducirá una regla de unidad si se aplica después de UNIT . La tabla muestra los órdenes admitidos.

Además, el aumento de tamaño de la gramática en el peor de los casos ^{[ nota 5 ]} depende del orden de transformación. Usando | G | para denotar el tamaño de la gramática original G , el aumento de tamaño en el peor de los casos puede variar de | G | ² a 22 ^|G| , dependiendo del algoritmo de transformación utilizado. ^{[ 8 ] : 7} El aumento de tamaño de la gramática depende del orden entre DEL y BIN . Puede ser exponencial cuando DEL se realiza primero, pero es lineal en caso contrario. UNIT puede incurrir en un aumento cuadrático en el tamaño de la gramática. ^{[ 8 ] : 5} Los ordenamientos START , TERM , BIN , DEL , UNIT y START , BIN , DEL , UNIT , TERM conducen al menor aumento (es decir, cuadrático).

Otra forma ^{[ 4 ] : 92 [ 10 ]} de definir la forma normal de Chomsky es:

Una gramática formal está en forma reducida de Chomsky si todas sus reglas de producción tienen la forma:

${\displaystyle A\rightarrow \,BC}$o

${\displaystyle A\rightarrow \,a}$,

dónde${\displaystyle A}$,${\displaystyle B}$y${\displaystyle C}$son símbolos no terminales y${\displaystyle a}$es un símbolo terminal . Al usar esta definición,${\displaystyle B}$o${\displaystyle C}$puede ser el símbolo de inicio. Solo aquellas gramáticas libres de contexto que no generan la cadena vacía pueden transformarse en la forma reducida de Chomsky.

En una carta donde propuso un término forma Backus-Naur (BNF), Donald E. Knuth insinuó que una "sintaxis BNF en la que todas las definiciones tienen tal forma puede decirse que están en 'Forma Normal de Floyd'",

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \mid \langle C\rangle } o

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \langle C\rangle } o

${\displaystyle \langle A\rangle$ ::=\,a} ,

dónde${\displaystyle \langle A\rangle }$,${\displaystyle \langle B\rangle }$y${\displaystyle \langle C\rangle }$son símbolos no terminales y${\displaystyle a}$es un símbolo terminal, porque Robert W. Floyd descubrió en 1961 que cualquier sintaxis BNF se puede convertir a la anterior. ^{[ 11 ]} Pero retiró este término, "ya que sin duda muchas personas han utilizado de forma independiente este hecho simple en su propio trabajo, y el punto es solo incidental a las consideraciones principales de la nota de Floyd". ^{[ 12 ]} Mientras que la nota de Floyd cita el artículo original de Chomsky de 1959, la carta de Knuth no lo hace.