Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 51 vistas

    3-5 CNF

    Cargado por

    Nilas Arcanister
    Este documento introduce la forma normal de Chomsky, un método para transformar gramáticas libres de contexto en una forma que permite algoritmos polinomiales para determinar si una palabra pertenece al lenguaje. Explica que la forma normal requiere que las gramáticas solo tengan producciones simples o dividan símbolos no terminales, y describe un algoritmo para transformar cualquier gramática libre de contexto a esta forma.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    3-5 CNF

    Cargado por

    Nilas Arcanister
    51 vistas15 páginas
    Este documento introduce la forma normal de Chomsky, un método para transformar gramáticas libres de contexto en una forma que permite algoritmos polinomiales para determinar si una palabra pertenece al lenguaje. Explica que la forma normal requiere que las gramáticas solo tengan producciones simples o dividan símbolos no terminales, y describe un algoritmo para transformar cualquier gramática libre de contexto a esta forma.

    Descripción original:

    Universidad de Cantabria - CURSO de TEORIA DE AUTOMATAS

    Título original

    3-5_CNF

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento introduce la forma normal de Chomsky, un método para transformar gramáticas libres de contexto en una forma que permite algoritmos polinomiales para determinar si una palabra pertenece al lenguaje. Explica que la forma normal requiere que las gramáticas solo tengan producciones simples o dividan símbolos no terminales, y describe un algoritmo para transformar cualquier gramática libre de contexto a esta forma.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    51 vistas15 páginas

    3-5 CNF

    Cargado por

    Nilas Arcanister
    Este documento introduce la forma normal de Chomsky, un método para transformar gramáticas libres de contexto en una forma que permite algoritmos polinomiales para determinar si una palabra pertenece al lenguaje. Explica que la forma normal requiere que las gramáticas solo tengan producciones simples o dividan símbolos no terminales, y describe un algoritmo para transformar cualquier gramática libre de contexto a esta forma.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 15

    Introduccin

    Forma Normal de Chomsky


    Algoritmo

    La Forma Normal de Chomsky


    Algoritmos Polinomiales para el Problema de la Palabra en
    CFL

    Universidad de Cantabria

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Esquema

    Introduccin

    Forma Normal de Chomsky

    Algoritmo

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Introduccin

    Hemos visto hasta aqu como demostrar si una palabra esta


    dentro de un lenguaje libre de contexto (CFL). El problema es
    que el algoritmo es de naturaleza exponencial. Como reducir
    la complejidad de ese algoritmo?

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Introduccin

    El problema bsico es que, si tenemos una gramtica muy


    general, no parece viable otra posibilidad que probar con todas
    las combinaciones de reglas gramaticales.
    Por lo tanto, hay que utilizar otro tipo de gramticas, que sean
    menos generales que las propias.

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Introduccin

    El problema bsico es que, si tenemos una gramtica muy


    general, no parece viable otra posibilidad que probar con todas
    las combinaciones de reglas gramaticales.
    Por lo tanto, hay que utilizar otro tipo de gramticas, que sean
    menos generales que las propias.

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Forma Normal de Chomsky

    Definicin (Forma Normal de Chomsky)


    Una gramtica libre de contexto G := (V , , Q0 , P) se dice que
    est en forma normal de Chomsky si es -libre y las nicas
    producciones (exceptuando, eventualmente, la nica
    produccin Q0 7 ), son exclusivamente de uno de los dos
    tipos siguientes.
    A 7 a, con A V y a ,
    A 7 CD, con A, C, D V .

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Preguntas

    Son estas gramticas libres?


    Tienen producciones simples?
    Tienen smbolos intiles?
    Se pueden detectar utilizando un autmata finito?

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Algoritmo

    Teorema (Transformacin a Forma Normal de Chomsky)


    Toda gramtica libre de contexto es equivalente a una
    gramtica libre de contexto en Forma Normal de Chomsky.
    Adems, esta equivalencia es algortmicamente computable.

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Algoritmo

    Supongamos que tenemos una gramtica G = (V , , Q0 , P)


    propia. Procederemos del modo siguiente:
    yP
    de smbolos no terminales y
    Definamos un par de clases V
    producciones.

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Algoritmo

    := V , P
    = y aadimos estas producciones
    Inicializar con V
    por defecto:
    sin modificar V
    .
    Si Q0 7 est en P, aadir Q0 7 a P
    Si en P hay una produccin del tipo A 7 a entonces,
    sin modificar V
    .
    aadir A 7 a a P
    Si en P hay una produccin del tipo A 7 CD, con
    sin modificar V
    .
    C, D V , entonces, aadir A 7 CD a P
    Simplemente, aadimos las producciones que cumplan la
    definicin.

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Algoritmo
    Finalmente, para cada produccin en P del tipo
    A 7 X1 Xk ,
    con Xi V que no sea de ninguno de los tres tipos
    anteriores realizar las tareas siguientes:

    Para cada i tal que Xi V , no modificar V


    una nueva variable
    Para cada i tal que Xi , aadir a V

    . Aadir a P

    Xi , distinta a todas las que ya estuvieran en V


    la produccin Xi 7 Xi en este caso.
    la produccin A 7 X 0 X 0 , donde X 0 viene
    Aadir a P
    1

    dada por:
    Xi0

    
    :=

    Xi ,
    si Xi V

    Xi , en otro caso
    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Si k = 2, no modificar.
    la produccin A 7 X 0 X 0 por
    Si k > 2, reemplazar en P,
    1
    k
    una cadena de producciones:
    A 7 X10 Y2 , Y2 7 X20 Y3 , , Yk 1 7 Xk0 1 Xk0 ,
    las variables {Y2 , . . . , Yk 1 }.
    aadiendo a V
    Esto termina con el algoritmo.

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Nota

    Obsrvese que los rboles de derivacin asociados a


    gramticas en forma normal de Chomsky son rboles binarios.

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Nota

    Este proceso algortmico es polinomial, otra vez, pero:


    Cuantas producciones nuevas se aaden en el peor de
    los casos?
    Se aaden variables intiles durante el proceso?
    Por qu pedimos que la gramtica sea propia como
    entrada del algoritmo?

    Forma Normal de Chomsky

    Introduccin
    Forma Normal de Chomsky
    Algoritmo

    Conclusiones

    Hemos estudiado la forma normal de Chomsky:


    La gramtica transformada sigue siendo propia.
    Las gramticas pueden aadir nuevas derivaciones a una
    misma palabra.
    El rbol de derivacin siempre ser binario, esto es muy
    importante.

    Forma Normal de Chomsky

    También podría gustarte