Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 72 vistas

    Auxiliar 8 Algoritmo CYK

    Cargado por

    Aldair Vasquez Chavez
    Este documento describe el algoritmo CYK, un algoritmo de parsing bottom-up para gramáticas libres de contexto. Se utiliza programación dinámica para determinar en tiempo O(n3|G|) si una palabra es generada por una gramática. El documento propone varios ejercicios para aplicar el algoritmo CYK y sus variaciones, incluyendo determinar derivaciones posibles, una derivación específica, y la derivación de costo mínimo cuando se asignan costos a las reglas.

    Copyright:

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

    Auxiliar 8 Algoritmo CYK

    Cargado por

    Aldair Vasquez Chavez
    72 vistas2 páginas
    Este documento describe el algoritmo CYK, un algoritmo de parsing bottom-up para gramáticas libres de contexto. Se utiliza programación dinámica para determinar en tiempo O(n3|G|) si una palabra es generada por una gramática. El documento propone varios ejercicios para aplicar el algoritmo CYK y sus variaciones, incluyendo determinar derivaciones posibles, una derivación específica, y la derivación de costo mínimo cuando se asignan costos a las reglas.

    Descripción original:

    rtyuiop´+

    Título original

    Auxiliar_8_Algoritmo_CYK

    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 describe el algoritmo CYK, un algoritmo de parsing bottom-up para gramáticas libres de contexto. Se utiliza programación dinámica para determinar en tiempo O(n3|G|) si una palabra es generada por una gramática. El documento propone varios ejercicios para aplicar el algoritmo CYK y sus variaciones, incluyendo determinar derivaciones posibles, una derivación específica, y la derivación de costo mínimo cuando se asignan costos a las reglas.

    Copyright:

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

    Auxiliar 8 Algoritmo CYK

    Cargado por

    Aldair Vasquez Chavez
    Este documento describe el algoritmo CYK, un algoritmo de parsing bottom-up para gramáticas libres de contexto. Se utiliza programación dinámica para determinar en tiempo O(n3|G|) si una palabra es generada por una gramática. El documento propone varios ejercicios para aplicar el algoritmo CYK y sus variaciones, incluyendo determinar derivaciones posibles, una derivación específica, y la derivación de costo mínimo cuando se asignan costos a las reglas.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 2

    Auxiliar 8 - Algoritmo CYK

    Curso: Teorı́a de la Computación


    Profesor: Jorge Pérez
    Auxiliares: Rodrigo Alonso, Caterina Muñoz
    8 de junio de 2014

    El algoritmo CYK (Cocke-Younger-Kasami) es un algoritmo de parsing bottom-up pa-


    ra GLC que utiliza programación dinámica1 . Este algoritmo nos permite saber en tiempo
    O(n3 |G|) si una gramática libre de contexto genera una palabra (previa conversión de la
    GLC a su FNC). En esta clase, veremos algunos usos de CYK.

    Considere la gramática en FNC definida por las reglas siguientes:

    S → AB | BC
    A → BA | a
    B → CC | b
    C → AB | a

    1. Use el algoritmo CYK para determinar si la gramática anterior genera las siguientes
    palabras:

    a) abba
    b) bbaa
    c) ababa
    d ) aaaaa
    e) aaaaaa

    2. Adapte el algoritmo CYK para obtener el número de derivaciones posibles de una


    palabra, y utilı́celo sobre las palabras anteriores.

    3. Modifique el algoritmo CYK para determinar alguna derivación para una palabra.
    Utilice el algoritmo modificado para obtener una derivación con la gramática anterior
    para las siguientes palabras:

    a) aaa
    b) bbaaa
    c) bababa

    4. Suponga ahora que cada uso de una regla tiene un costo asociado. Modifique el algorit-
    mo CYK, esta vez para obtener la derivación de costo mı́nimo para una palabra (usando
    como función de costo de una derivación la suma entre el costo de la regla y el costo de
    1
    Programación dinámica es una técnica que consiste en dividir un problema complejo en varios problemas
    más sencillos. Esto se realiza de manera tal que, en caso de existir subproblemas que se traslapan, estos
    problemas se resuelven una sola vez y se almacena el resultado para su posterior consulta. Esta técnica
    permite resolver esos problemas en tiempo polinomial, de lo contrario, dependiendo del problema, tomarı́a
    tiempo exponencial. Comúnmente, esta técnica se revisa en cursos de Algoritmos, y se utiliza a menudo en
    competencias de programación.

    1
    las subderivaciones). Utilice el algoritmo modificado sobre las palabras a continuación,
    considerando las siguientes reglas (con su costo respectivo entre paréntesis):

    S → aZ(5) | Y e(8)
    X → cd(7) | aX(4)
    Y → Xe(5) | ZX(7)
    Z → bY (9) | ab(1)

    a) abcde
    b) abaacde
    c) abbcdecd

    También podría gustarte