Forma normal de Chomsky

En la teoría del lenguaje formal, se dice que una gramática independiente del contexto, G, está en la forma normal de Chomsky (descrita por primera vez por Noam Chomsky) si toda su producción las reglas son de la forma:

A → BC, o

A → a, o

S → ε,

donde A, B y C son símbolos no terminales, la letra a es un símbolo terminal (un símbolo que representa un valor constante), S es el símbolo de inicio y ε denota la cadena vacía. Además, ni B ni C pueden ser el símbolo de inicio, y la tercera regla de producción solo puede aparecer si ε está en L( G), el lenguaje producido por la gramática libre de contexto G.

Cada gramática en la forma normal de Chomsky es independiente del contexto y, a la inversa, toda gramática independiente del contexto se puede transformar en una equivalente que está en la forma normal de Chomsky y tiene un tamaño no mayor que el cuadrado de la gramática original.;s tamaño.

Convertir una gramática a la forma normal de Chomsky

Para convertir una gramática a la forma normal de Chomsky, se aplica una secuencia de transformaciones simples en un cierto orden; esto se describe en la mayoría de los libros de texto sobre teoría de autómatas. La presentación aquí sigue a Hopcroft, Ullman (1979), pero está adaptada para usar los nombres de transformación de Lange, Leiß (2009). Cada una de las siguientes transformaciones establece una de las propiedades requeridas para la forma normal de Chomsky.

INICIO: Eliminar el símbolo de inicio de los lados derechos

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.

TÉRMINO: Eliminar reglas con terminales no solitarios

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 terminal, un nuevo símbolo no terminal N_a, y una nueva regla

N_a → a.

Cambiar 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, reemplace simultáneamente cada uno de ellos por su símbolo no terminal asociado. Esto no cambia el lenguaje producido por la gramática.

BIN: Elimina los lados derechos con más de 2 no terminales

Reemplazar cada regla

A → X₁ X₂... X_n

con más de 2 no terminales X₁,...,X_n por 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.

DEL: eliminar las reglas ε

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 determina el conjunto de todos los no terminales que derivan de ε. Hopcroft y Ullman (1979) llaman a tales no terminales anulables, y los calculan de la siguiente manera:

• Si una regla A → ε existe, entonces A es nulo.
• Si una regla A → X₁... X_n existe, y cada uno X_i es nula, entonces A también es nulo.

Obtenga una gramática intermedia reemplazando cada regla

A → X₁... X_n

por todas las versiones con alguna X_i anulable omitida. Al eliminar en esta gramática cada regla ε, a menos que su lado izquierdo sea el símbolo de inicio, se obtiene la gramática transformada.

Por ejemplo, en la siguiente gramática, con el símbolo de inicio S₀,

S₀ → AbB Silencio C

B → AA Silencio AC

C → b Silencio c

A → a ε

el no terminal A, y por lo tanto también B, es anulable, mientras que ni C ni S₀ es. Por tanto, se obtiene la siguiente gramática intermedia:

S₀ → AbB Silencio AbB Silencio AbB Silencio AbB Silencio C

B → AA Silencio AA Silencio AA Silencio AεA Silencio AC Silencio AC

C → b Silencio c

A → a ε

En esta gramática, todas las reglas ε se han "en línea en el sitio de llamada". En el siguiente paso, por lo tanto, se pueden eliminar, lo que da como resultado la gramática:

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

B → AA Silencio A Silencio AC Silencio C

C → b Silencio c

A → a

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

UNIDAD: Eliminar reglas de unidad

Una regla de unidad es una regla de la forma

A → B,

donde A, 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, añadir regla

A → X₁... X_n

a menos que se trate de una regla de unidad que ya se eliminó (o se eliminará). La omisión del símbolo no terminal B en la gramática resultante es posible debido a que B es miembro del cierre de unidad del símbolo no terminal A.

Orden de las transformaciones

Conservación mutua
de resultados de transformación

Transformación X siempre conserva ()Y) Resp. puede destruir ()N) el resultado de Y:
Y X	START	TERM	BIN	DEL	UNIT
START
TERM
BIN
DEL
UNIT				()Y)*
*UNIT preserva el resultado de DEL si START había sido llamado antes.

Al elegir el orden en el que se aplicarán las transformaciones anteriores, se debe tener en cuenta que algunas transformaciones pueden destruir el resultado logrado por otras. Por ejemplo, START volverá a introducir una regla de unidad si se aplica después de UNIT. La tabla muestra qué pedidos se admiten.

Además, el tamaño de la gramática en el peor de los casos depende del orden de transformación. Usando |G| para indicar el tamaño de la gramática original G, el tamaño ampliado en el peor de los casos puede oscilar entre |G|² a 2^{2 |G|}, dependiendo del algoritmo de transformación utilizado. La ampliación del tamaño de la gramática depende del orden entre DEL y BIN. Puede ser exponencial cuando DEL se hace primero, pero es lineal en caso contrario. UNIT puede incurrir en una ampliación cuadrática en el tamaño de la gramática. Los pedidos START, TERM, BIN, DEL, UNIT y START, BIN, DEL, UNIT, TERM conducen al golpe mínimo (es decir, cuadrático) -hasta.

Ejemplo

Árbol de sintaxis abstracto de la expresión aritmética "a^2+4*b" wrt. la gramática de ejemplo (arriba) y su forma normal Chomsky (inferior)

La siguiente gramática, con el símbolo de inicio Expr, describe una versión simplificada del conjunto de todas las expresiones aritméticas sintácticas válidas en lenguajes de programación como C o Algol60. Tanto number como variable se consideran aquí símbolos de terminal por simplicidad, ya que en una interfaz de compilación el analizador no suele tener en cuenta su estructura interna. El símbolo de terminal "^" exponenciación denotada en Algol60.

Gastos	→ Término	Silencio Gastos AddOp Término	Silencio AddOp Término
Término	→ Factor	Silencio Término MulOp Factor
Factor	→ Primaria	Silencio Factor ^ Primaria
Primaria	→ Número	Silencio variable	SilencioGastos)
AddOp	→ +	Silencio
MulOp	→ *	Silencio

En el paso "INICIAR" del algoritmo de conversión anterior, solo se agrega una regla S₀→Expr a la gramática. Después del paso "TERM", la gramática se ve así:

S0	→ Gastos
Gastos	→ Término	Silencio Gastos AddOp Término	Silencio AddOp Término
Término	→ Factor	Silencio Término MulOp Factor
Factor	→ Primaria	Silencio Factor PowOp Primaria
Primaria	→ Número	Silencio variable	Silencio Abierto Gastos Cerca
AddOp	→ +	Silencio
MulOp	→ *	Silencio
PowOp	→ ^
Abierto	→
Cerca	→)

Después del paso "BIN", se obtiene la siguiente gramática:

S0	→ Gastos
Gastos	→ Término	Silencio Gastos AddOp_Term	Silencio AddOp Término
Término	→ Factor	Silencio Término MulOp_Factor
Factor	→ Primaria	Silencio Factor PowOp_Primary
Primaria	→ Número	Silencio variable	Silencio Abierto Expr_Close
AddOp	→ +	Silencio
MulOp	→ *	Silencio
PowOp	→ ^
Abierto	→
Cerca	→)
AddOp_Term	→ AddOp Término
MulOp_Factor	→ MulOp Factor
PowOp_Primary	→ PowOp Primaria
Expr_Close	→ Gastos Cerca

Dado que no hay reglas ε, el paso "DEL" no cambia la gramática. Después del paso "UNIT", se obtiene la siguiente gramática, que está en la forma normal de Chomsky:

S0	→ Número	Silencio variable	Silencio Abierto Expr_Close	Silencio Factor PowOp_Primary	Silencio Término MulOp_Factor	Silencio Gastos AddOp_Term	Silencio AddOp Término
Gastos	→ Número	Silencio variable	Silencio Abierto Expr_Close	Silencio Factor PowOp_Primary	Silencio Término MulOp_Factor	Silencio Gastos AddOp_Term	Silencio AddOp Término
Término	→ Número	Silencio variable	Silencio Abierto Expr_Close	Silencio Factor PowOp_Primary	Silencio Término MulOp_Factor
Factor	→ Número	Silencio variable	Silencio Abierto Expr_Close	Silencio Factor PowOp_Primary
Primaria	→ Número	Silencio variable	Silencio Abierto Expr_Close
AddOp	→ +	Silencio
MulOp	→ *	Silencio
PowOp	→ ^
Abierto	→
Cerca	→)
AddOp_Term	→ AddOp Término
MulOp_Factor	→ MulOp Factor
PowOp_Primary	→ PowOp Primaria
Expr_Close	→ Gastos Cerca

La N_a introducida en el paso "TERM" son PowOp, Abrir y Cerrar. El A_i introducido en el paso "BIN" son AddOp_Term, MulOp_Factor, PowOp_Primary y Expr_Close.

Definición alternativa

Forma reducida de Chomsky

Otra manera 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 son de la forma:

A→ → BC{displaystyle Arightarrow ,BC} o

A→ → a{displaystyle Arightarrow ,a},

Donde A{displaystyle A}, B{displaystyle B} y C{displaystyle C} son símbolos no finales, y a{displaystyle a} es un símbolo terminal. Al utilizar esta definición, B{displaystyle B} o C{displaystyle C} puede ser el símbolo de inicio. Sólo esas gramáticas sin contexto que no generan la cadena vacía pueden transformarse en forma reducida Chomsky.

Forma normal de Floyd

En una carta en la que proponía un término forma Backus-Naur (BNF), Donald E. Knuth insinuaba una sintaxis BNF en la que todas las definiciones tienen tal forma y se puede decir que está en 'Floyd Forma normal'",

.. A.. ::=.. B.. ▪ ▪ .. C.. {displaystyle langle Arangle:=,langle Brangle mid langle Crangle } o

.. A.. ::=.. B.. .. C.. {displaystyle langle Arangle:=,langle Brangle langle Crangle } o

.. A.. ::=a{displaystyle langle Arangle:=,a},

Donde .. A.. {displaystyle langle Arangle }, .. B.. {displaystyle langle Brangle } y .. C.. {displaystyle langle Crangle } son símbolos no finales, y a{displaystyle a} es un símbolo terminal, porque Robert W. Floyd encontró cualquier sintaxis BNF se puede convertir a la anterior en 1961. Pero retiró este término, "ya que sin duda muchas personas han utilizado independientemente este simple hecho en su propio trabajo, y el punto es sólo incidental a las principales consideraciones de la nota de Floyd." Mientras que la nota de Floyd cita el artículo original de Chomsky en 1959, la carta de Knuth no.

Solicitud

Además de su importancia teórica, la conversión CNF se usa en algunos algoritmos como un paso de preprocesamiento, por ejemplo, el algoritmo CYK, un análisis de abajo hacia arriba para gramáticas sin contexto y su variante CKY probabilística.