Forma normal de Chomsky

La forma normal de Chomsky es una propiedad de una gramática formal si todas sus salidas tienen la forma:

A

{\ estilo de visualización \ flecha derecha \, BC}

A

{\ estilo de visualización \ flecha derecha \, \ alfa}

S

{\ estilo de visualización \ flecha derecha \, \ épsilon}

donde y no son terminales, es un carácter terminal (que representa un valor constante), es un carácter de inicio y es la cadena vacía . Además, ni , ni puede ser un carácter de inicio. $A$ $B$ $C$ $\alfa$ $S$ $\epsilon$ $B$ $C$

Cada gramática en la forma normal de Chomsky es independiente del contexto y , a la inversa, cada gramática independiente del contexto se puede convertir de manera eficiente a una gramática equivalente en la forma normal de Chomsky.

Con la excepción de una regla posible (que se usa cuando la gramática puede producir la cadena vacía), todas las reglas gramaticales en la forma normal de Chomsky no son abreviaturas; es decir, en el proceso de generar una cadena, cada cadena de terminales y no terminales siempre tiene la misma longitud que la anterior o un elemento más. Imprimir una cadena de longitud siempre requiere pasos exactos . Además, dado que todas las reglas de inferencia no terminales traducen un no terminal en exactamente un terminal o en exactamente dos no terminales, el árbol de análisis basado en la gramática de forma normal de Chomsky es un árbol binario cuya altura está limitada por la longitud de la cadena. $S$ ${\ estilo de visualización \ flecha derecha \, \ épsilon}$ $norte$ $2n-1$

Debido a estas propiedades, muchas demostraciones en la teoría de lenguajes formales y computabilidad utilizan la forma normal de Chomsky. Estas propiedades también sirven como base para varios algoritmos eficientes; por ejemplo, el algoritmo CYK que determina si una gramática determinada puede generar una cadena determinada utiliza la forma normal de Chomsky.

Nombrado así por Noam Chomsky , el lingüista estadounidense que propuso la jerarquía de Chomsky .

Definición alternativa

Algunas fuentes definen la forma normal de Chomsky de manera algo diferente.

Una gramática formal está en la forma normal de Chomsky si todas sus salidas tienen la forma:

A

{\ estilo de visualización \ flecha derecha \, BC}

A

{\ estilo de visualización \ flecha derecha \, \ alfa}

donde , y son no terminales, y es el símbolo terminal de . Cuando se usa esta definición , y pueden ser caracteres iniciales. $A$ $B$ $C$ $\alfa$ $B$ $C$

Esta definición difiere de la anterior en que excluye la posibilidad de generar una cadena vacía . Sigue siendo cierto que cualquier gramática independiente del contexto que genera un lenguaje puede transformarse efectivamente en una forma normal de Chomsky que genera . La principal ventaja de la última definición es que las demostraciones en general se simplifican un poco, ya que cada paso de derivación nunca reduce la longitud de la cadena resultante. Por supuesto, su inconveniente es que requiere una consideración separada del caso cuando la gramática genera . $\epsilon$ $L$ ${\displaystyle L-\{\épsilon \))$ $\epsilon$

Literatura

Michael Sipser Introducción a la Teoría de la Computación . - PWS Publishing, 1997. - ISBN 0-534-94728-X . (Páginas 98-101 de la sección 2.1: gramáticas libres de contexto. Página 156.)
Juan Martín . Introducción a los Lenguajes y la Teoría de la Computación . - McGraw-Hill Education , 2003. - ISBN 0-07-232200-4 . (Páginas 237-240 del apartado 6.6: formularios simplificados y formularios normales.)
John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría de los autómatas, lenguajes y computación , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (Véase el capítulo 4.)
Michael HarrisonIntroducción a la Teoría del Lenguaje Formal (neopr.) . - Addison-Wesley , 1978. - ISBN 978-0201029550 . (Páginas 103-106.)