forma normal chomski

Ejercicio Guía para obtener FNC y FNG
Este documento tiene como fin mostrar la forma de obtener la Forma Normal de Chomsky (FNC o
también CNF) y la Forma Normal de Greibach (FNG o también GNF) de una gramática dada, mediante un
ejercicio explicativo.
La gramática en cuestión del ejercicio es la siguiente:
S → A | BCa | aDcd | EDF
A → aAb | c
B → CD | b | ECd | Ad
C → Cc | Bb | AaE | ε
D→ aDd | Dd | ε
E → aaEB | EFG
F → aFd | d
Durante este ejercicio, la gramática irá sufriendo modificaciones que en algunos casos mantendrá a
su lenguaje intacto y en otras lo alterará.

Forma Intermedia de Chomsky
Antes de empezar con el proceso para obtener la FNC de una gramática, debemos dejar a dicha
gramática en un estado intermedio, al cual podemos llamar forma intermedia de Chomsky,aunque no suele
llamársele por ningún nombre. De todas formas, en este paso, lo que vamos a tratar de obtener es una
gramática libre de símbolos inútiles, producciones ε y producciones unitarias. Cuando ya hayamos limpiado
a nuestra gramática de estas cosas, podremos empezar a obtener su FNC.

Eliminando Símbolos Inútiles
En este paso, eliminaremos todos aquellos símbolos que sean inútiles.Hay dos tipos de símbolos
inútiles: los no generadores y los no alcanzables.

Eliminando Símbolos No Generadores
Para eliminar símbolos no generadores, primero tratamos de identificar todos aquellos símbolos que
sean generadores. Aquellas variables que no podamos determinar que son generadoras pasarán a ser
símbolos no generadores y se eliminarán.
Por definición, todos los símbolosterminales de una gramática son generadores, ya que se generan
a sí mismos.
También será un símbolo generador toda aquella variable que tenga por lo menos una producción
que esté conformada únicamente de símbolos generadores. El string vacío ε se considera un símbolo
generador.
Identifiquemos en nuestra gramática nuestros símbolos generadores: A es generador, ya que tiene
la producción A → c. Tambiénlo es B, ya que tiene B → b. C y D son generadores, ya que tienen la
producción vacía C → ε y D → ε, respectivamente. F tiene la producción F → d. Por último, S tiene la
producción S → BCa, donde tanto B, C como a son símbolos generadores, por lo tanto S es generador
también.
E no es un símbolo generador. Tiene dos producciones, es verdad. Una es E → aaEB y la otra es
E → EFG, y en las doshay presentes símbolos generadores, como por ejemplo a y B en la primera
producción y F en la segunda. Pero ninguna de dichas producciones está completamente compuesta por
símbolos generadores. Miremos por ejemplo la segunda producción: está presente la variable G, que no
tiene ninguna producción asociada, por lo que es incapaz de ser un símbolo generador. Descartamos esta
producción entonces.Veamos la primera producción, tal vez descubramos algo: Mmmmh, tiene a la variable

E entre medio, la cual todavía no sabemos si es generadora. Qué recursivo, ¿eh? Pues bueno, la recursión
llega hasta ahí: No sabemos si E es generador y no hay ninguna otra producción de E que nos ayude a
verificar esto, así que la primera producción no nos sirve para determinar a E como un símbolo generador,y
como no podemos verificar que E es un símbolo generador, entonces lo consideramos como un símbolo NO
generador. Procedemos ahora a eliminar las variables E y G de la gramática y a todas las producciones en
las que estén presentes. O sea, eliminamos S → EDF , B → ECd, C → AaE, E → aaEB y E → EF. La
gramática queda como sigue:
S → A | BCa | aDcd
A → aAb | c
B → CD | b | Ad
C → Cc | Bb | εD → aDd | Dd | ε
F → aFd | d
Puede que al lector le importe saber que no se altera el lenguaje de la gramática cuando se eliminan
los símbolos no generadores.

Eliminando Símbolos No Alcanzables
Puede que, desde un principio o por producto de la eliminación de algunos símbolos no
generadores, nuestra gramática presente símbolos no alcanzables o, dicho de otras palabras, símbolos que...