Scribd
Cargar
587 vistas6 páginas

Forma Normal de Chomsky

La forma normal de Chomsky (FNC) es una forma canónica para las gramáticas libres de contexto en la que cada producción es de la forma X→YZ o X→a. El documento explica que cualquier gramática libre de contexto G puede transformarse en una gramática equivalente G' que está en FNC mediante la eliminación de producciones nulas, unitarias e inútiles y la división de producciones con lados derechos mixtos en cadenas de producciones.

Cargado por

Tomás Hernández
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
587 vistas6 páginas

Forma Normal de Chomsky

La forma normal de Chomsky (FNC) es una forma canónica para las gramáticas libres de contexto en la que cada producción es de la forma X→YZ o X→a. El documento explica que cualquier gramática libre de contexto G puede transformarse en una gramática equivalente G' que está en FNC mediante la eliminación de producciones nulas, unitarias e inútiles y la división de producciones con lados derechos mixtos en cadenas de producciones.

Cargado por

Tomás Hernández
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Forma Normal de Chomsky (FNC)

Una gramtica est en la forma normal de Chomsky


(FNC) si cada produccin (a excepcin de S0, si es que
existe) es de una de las dos siguientes formas:
XYZ

o bien

Xa

donde, como de costumbre, X,Y,ZV, aT.

S AS
Sa
A SA
Ab

Est en FNC

No est en FNC

S AS
S AAS
A SA
A aa

Forma Normal de Chomsky (FNC)


Teorema: Para toda gramtica de libre contexto G,
existe una gramtica de libre contexto G' en forma
normal de Chomsky que es equivalente a G (es decir,
L(G)=L(G')).

Para demostrarlo, tenemos que ver que podemos


transformar cualquier GLC hasta que quede en FNC.
1. Eliminamos las producciones nulas, unitarias, e intiles.
2. Eliminamos los lados derechos "mixtos":

Forma Normal de Chomsky (FNC)


Para eliminar los lados derechos mixtos:
Creamos una nueva variable T por cada terminal .
Reemplazamos cada por el T respectivo, y
agregamos un produccin T.

S ABa
A aab
B Ac
Ojo: si alguna produccin ya era de la
forma X, la dejamos as (no la
cambiamos a XT). As evitamos
introducir producciones unitarias.

S ABTa

A TaTaTb
B ATc
Ta a
Tb b
Tc c

Forma Normal de Chomsky (FNC)


3. Reemplazamos toda produccin de la forma
AC1C2...Cn
por una cadena de producciones
AC1V1
V1C2V2
...
Vn-2Cn-1 Cn
donde los V1,...,Vn-2 son nuevas variables, intermedias.

Forma Normal de Chomsky (FNC)

S ABTa
A TaTaTb
B ATc
Ta a
Tb b
Tc c

S AV1
V1 BTa
A TaV2
V2 TaTb
B ATc
Ta a
Tb b
Tc c

Forma Normal de Chomsky (FNC)


Y listo.
Llevar GLC a la forma normal de
Chomsky es relativamente fcil.
Tener la GLC en FNC sirve para varias
cosas, prcticas y tericas.
La ms importante: para parsear en
tiempo polinomial en |w|.

S AV1
V1 BTa
A TaV2
V2 TaTb
B ATc
Ta a
Tb b
Tc c

También podría gustarte