Metodo chomsky

1.6. FORMA NORMAL DE CHOMSKY |
OBJETIVO
Comprender la manera en que podemos convertir una gramática independiente del contexto a una gramática de la Forma Normal de Chomsky.
JUSTIFICACIÓN
Lasgramáticas tienen ciertas similitudes, pero cuando no es así es necesario realizar una serie de pasos los cuales nos permitan obtener dos gramáticas diferentes y que lleguen al mismo resultado.INTRODUCCIÓN
Las gramáticas se pueden expresar de diferentes formas, en ocasiones podemos llegar al mismo resultado utilizando gramáticas que difieren en su estructura, una norma para estandarizar lasgramática es la Forma Normal de Chomsky.
CONTENIDO
Teorema 2.4
Si L es un lenguaje independiente del contexto que no contiene la cadena vacía, entonces existe una gramática G independiente del contextotal que L(G)=L y el lado derecho de cualquier regla de reescritura en G consiste en un solo terminal o exactamente dos no terminales.
Se dice que una gramática cuyas reglas de reescritura seadhieren a las restricciones del teorema 2.4 tiene la FORMA NORMAL DE CHOMSKY (FNC o CNF), llamada así en honor a Noam Chomsky. Por ejemplo la siguiente gramática cuyo símbolo inicial es S tiene la formanormal de Chomsky.
SXM |
MSY |
Xx |
Yy |
 
Mientras que la siguiente gramática que genera el mismo lenguaje no la tiene
SxSy |
Sxy |
Pasos para obtener la forma normal de ChomskyConsidere la siguiente gramática
SzMz |
MN |
MyMy |
Nx |
S zMz zyMyz zyNyz zyxyz
Paso 1
Introducir los nuevos no terminales YZ y convertir la gramática anterior en la siguiente:
SZMZ |
MN|
MYMY |
Zz |
Yy |
Nx |
Paso 2
Lo siguiente es reemplazar la regla SZMZ por el par de reglas SZR; RMZ, mientras que MYMY se reemplaza por MYP; PMY para obtener la siguiente gramática:
SZR|
RMZ |
MN |
MYP |
PMY |
Zz |
Yy |
Nx |
 
Paso 3
Finalmente la regla MN se reemplaza por la regla Mx, produciendo así la siguiente gramática ya que tiene la forma normal de...