EL TEMA Formas Normales De Chomsky SE ENCUENTRA ESPERANDO TUS CONOCIMIENTOS.
Forma normal de Chomsky
Def.- Una GIC está en Forma normal de Chomsky (FNC) si:
nNo contiene producciones e. nTodas las producciones son de la forma: wA®a; aÎS. wA®BC; B y C son no terminales. Observe que todo árbol de derivación para esta forma normal es binario, excepto para las hojas.
Si G es una GIC y eÏL(G), G puede ser transformada a FNC. Para ello elimine: nTodas las producciones e. nTodos los símbolos inútiles. nTodas
Eliminando terminales para FNC Si se tiene una producción de la forma A®w, donde w=X 1 X 2?…Xn, donde cada Xi puede ser terminal o no terminal, se hará lo siguiente: nSi Xi es símbolo terminal, llamado s, sustituya Xi por un no terminal Cs y añada la producción Cs ® s. Después de esta transformación, todas las producciones A®w tienen en w un terminal o una cadena de no terminales.
Eliminando no terminales para FNC Para la última etapa en la transformación de G a FNC, se deben eliminar las cadenas con más de dos no terminales del lado derecho de una producción. Para ello, si A®B 1 B 2?…Bn es una producción con n≥2, la reemplazaremos por n-1 producciónes: nA®B 1 D 1? nD1®B 2 D 2? n… nDn-2®Bn-1Bn Donde los Di serán nuevos terminales.
Ejemplo de FNC Ej.- Considere la siguiente GIC, que no contiene producciones e, unitarias o símbolos inútiles: nS®bA|aB nA®bAA|aS|a nB®aBB|bS|b
Ej.- (Cont…) Después de la primer transformación, la gramática se convierte en: nS®CbA|CaB nA®CbAA|CaS|a nB®CaBB|CbS|b nCa®a nCb® b
Ej.- (Cont…) Después de la última transformación, la gramática se convierte en: nS®CbA|CaB nA®Cb D 1?|CaS|a nB®Ca D 2?|CbS|b nCa®a nCb® b nD1®AA nD2®BB
¿Qué hacer si eÎL(G)? Si L contiene e, se puede obtener una GIC en FNC para L-ē y después añadir, la producción S®e. La gramática resultante estará en FNC exceptuando la producción e.
FORMA NORMAL DE CHOMSKY
Ejemplo:
Gramática: A → Ac Donde: A - Es un no Terminal A → w Ac - Es la derivación del no Terminal A
Gramática en Forma Normal de Chomsky: A → AZ A → w Z → c
Pasos para la 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 A
2º Eliminamos reglas no productivas
Una regla no productiva consiste en un No Terminal que nunca es accesible desde el No Terminal principal y sus respectivas derivaciones, del mismo o de las que provoquen sus No Terminal que se encuentren en su propia derivación. Un ejemplo de una regla no productiva seria:
A → AZ W → X Z → c
En el ejemplo anterior el No Terminal W es una regla no productiva porque no es accesible desde el No Terminal principal que es A, ni de su derivación correspondiente que es AZ. Nota: Este paso es omitido en el programa, por lo que no se verifica si un No Terminal es improductivo, por lo tanto, el usuario debe asegurarse de no introducir éste tipos de reglas.
3º Se procede a dar el formato correspondiente de la FNC.
La FNC (Forma Normal de Chomsky) sigue dos reglas básicas y únicas para tener el formato debido, estás son:
1) Un No Terminal solo puede derivarse en otros dos No Terminales.
2) Un No Terminal solo puede derivar en un Terminal.
Para la explicación de estas dos propiedades procedemos con un ejemplo:
Tenemos la siguiente gramática:
A → cB+ B → q
Nota: La gramática anterior no tiene ni reglas unitarias ni reglas no productivas, con lo que procedemos con el paso 3º.
Observemos la primera producción:
A → cB+
1) Este No Terminal A deriva en cB+ donde como primer elemento de esta es un elemento Terminal, entonces procedemos a crear un No Terminal nuevo con este elemento y se lo agregamos al no Terminal A, respetando el orden de la gramática.
A → ZB+ Z → c
2) Una de las propiedades para la FNC es que un No Terminal solo puede derivar en otros dos No terminales, en nuestro ejemplo, tenemos el No Terminal A que deriva en ZB+, este contiene otro elemento terminal más, creamos un nuevo No Terminal para respetar la propiedad anteriormente descrita.
A → ZY Z → c Y → B+
3) Podemos ver que los No Terminal A y Z cumplen con las propiedades de la FNC, excepto el No Terminal Y que deriva en un No Terminal y un Terminal, por lo que procedemos a crear el último No Terminal que cumpla la FNC.
A → ZY Z → c Y → BX X → +
Por lo que se obtiene como resultado:
A → ZY Z → c Y → BX X → + B → q
ITP. Pinotepa RMNC