Forma Normal De Chomsky

Forma normal de Chomsky

Chomsky propuso la gramática universal, disciplina que situó la sintaxis en el centro de la investigación lingüística.

Denominó gramática universal al conjunto de reglas innatas que permite traducir combinaciones de ideas a combinaciones de palabras.

Su lingüística es una teoría de la adquisición individual del lenguaje e intenta ser una explicación de las estructuras y principios más profundos del lenguaje.

Como ya conocemos, existen gramáticas de muy diferentes formas que generan un mismo lenguaje. El hecho de no restringir la forma de las reglas de tipo 2 tiene interés en los casos en que se desea diseñar una gramática para un lenguaje dado. Sin embargo, cuando se desea desarrollar demostraciones de ciertas propiedades de los lenguajes incontextuales o se desea desarrollar algoritmos eficientes que operen sobre gramáticas incontextuales, interesa imponer ciertas restricciones en las formas de las reglas de la gramática. Para ello se introducen las definiciones y los algoritmos de obtención de las formas normales para las gramáticas incontextuales. En concreto, vamos a estudiar la conocida como Forma Normal de Chomsky (FNC). El objetivo principal de esta práctica es el estudio e implementación de los algoritmos que permiten obtener una gramática incontextual en FNC a partir de una gramática incontextual sin λ-reglas ni reglas simples

Una gramática libre de contexto G= (V,T,P,S) se dice estar en forma normal de Chomsky si sus producciones son de cualquiera de las dos formas con , o bien con y .

Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía se puede transformar en una gramática libre de contexto G'=(V',T,P',S') en forma normal de Chomsky.

En efecto, dada una gramática G, para transformar a G en una gramática G'' sin variables inútiles ni producciones vacías ni producciones unitarias equivalente a G. A las producciones que quedasen de la forma con y las dejamos sin cambio alguno. A cada producción de la forma, con y, la transformamos en una sucesión de producciones de la forma siguiente: A cada símbolo terminal que aparezca en la palabra le asociamos una variable nueva Xa e incorporamos la producción. Así pues las producciones que no sean de la forma con X variable y a terminal, han de ser de la forma, con todos variables. Para cada una de estas últimas producciones introducimos k-2 nuevas variables e incorporamos la sucesión de producciones.

Pasos para la transformación de una gramática a la FNC

1º Eliminamos reglas unitarias.

A -> Ac

A -> w

Primero verificamos si en la gramática no hay reglas unitarias que obstruyan el desarrollo de FNC. Un ejemplo de una regla unitaria seria:

A -> X

X -> z

Como se puede observar, un No Terminal A deriva en otro No Terminal X, que a su vez deriva en un Terminal z, esto es redundante y por lo tanto se procede a eliminar el No Terminal X y pasando el Terminal z al No Terminal

...