Algoritmo CYK


Algoritmo CYK

El algoritmo de Cocke-Younger-Kasami (CYK) determina si una cadena puede ser generada por una gramática libre de contexto y, si es posible, cómo puede ser generada. Este proceso es conocido como análisis sintáctico de la cadena. El algoritmo es un ejemplo de programación dinámica.

La versión estándar de CYK reconoce lenguajes definidos por una gramática libre de contexto escrita en la forma normal de Chomsky (CNF). Cualquier gramática libre de contexto puede ser convertida a CNF sin mucha dificultad, CYK puede usarse para reconocer cualquier lenguaje libre de contexto. Es posible extender el algoritmo CYK para que trabaje sobre algunas gramáticas libre de contexto no escritas como CNF. Esto puede hacerse para mejorar la ejecución, aunque hace el algoritmo más difícil de entender.

En el peor caso asintótico la complejidad temporal de CYK es de Θ(n3), donde n es la longitud de la cadena analizada. Esto hace a éste algoritmo uno de los más eficientes (en estos términos) en el reconocimiento de los lenguajes libres de contexto. Sin embargo, existen otros algoritmos con un mejor funcionamiento para ciertos subconjuntos de los lenguajes libres de contexto.

Contenido

El algoritmo

El algoritmo de CYK es un algoritmo de análisis ascendente. y su importancia teórica viene dada al poder usarse para probar que el problema de pertenencia a los lenguajes libres de contexto es decidible.

El algoritmo de CYK para el problema de pertenencia es el siguiente:

Let the input string consist of n letters, a1... an.
Let the grammar contain r terminal and nonterminal symbols R1... Rr. 
This grammar contains the subset Rs which is the set of start symbols.
Let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
For each i = 1 to n
  For each unit production Rj → ai, set P[i,1,j] = true.
For each i = 2 to n -- Length of span
  For each j = 1 to n-i+1 -- Start of span
    For each k = 1 to i-1 -- Partition of span
      For each production RA -> RB RC
        If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
If any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs)
  Then string is member of language
  Else string is not member of language

Informalmente

En términos informales, este algoritmo considera todas las posibles subsecuencias de una secuencia de palabras y establece P[i, j, k] a verdadero si la subsecuencia de palabras que empiezan desde i de longitud j puede ser generada desde Rk. Una vez consideradas las subsecuencias de longitud 1, se continúa con las de longitud 2, y así sucesivamente. Para subsecuencias de longitud 2 o mayor, se considera cada posible partición de la subsecuencia en dos partes, y se comprueba si existe alguna regla P → Q R en la que Q concuerda con la primera parte y R con la segunda. Si es así, se establece que P concuerda con la subsecuencia completa. Una vez que este proceso se complete, la frase es reconocida por la gramática si la subsecuencia que contien la frase completa concuerda con el símbolo inicial.

Tabla de CYK
S
VP
 
S
VP PP
S NP NP
NP V, VP Det. N P Det N
she eats a fish with a fork

Extensión del algoritmo

Es fácil extender el algoritmo para que no sólo determine si una frase pertenece a un lenguaje, sino que también construya un árbol sintáctico, guardando los nodos del árbol como elementos de un array, en vez de como booleanos. Puesto que las gramáticas pueden ser ambiguas, es necesario guardar una lista de nodos para cada uno de los posibles árboles sintácticos. Así, el resultado final es un bosque con todos los posibles árboles sintácticos.

También es posible extender el algoritmo CYK para analizar cadenas usando gramáticas libres de contexto con pesos y gramáticas libres de contexto probabilísticas. Los pesos o probabilidades serán guardados en la tabla P en vez de los valores booleanos. De esta manera P[i, j, A] contendrá el mínimo peso (máxima probabilidad) de que la subcadena desde i hasta j pueda ser derivada por A. Otras extensiones permiten al algoritmo enumerar todos los posibles análisis de una frase ordenándolos de menor a mayor peso (mayor a menor probabilidad).

Referencias

  • John Cocke and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
  • T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
  • Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n3. Information and Control 10(2): 189–208.

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Algoritmo de Earley — El algoritmo de Earley[1] es un algoritmo no determinístico de análisis sintáctico para las gramáticas libres de contexto descrito originalmente por Jay Earley. Se ordena, a los lados de los algoritmos CYK y GLR, entre los algoritmos que usan la… …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… …   Wikipedia Español

  • Gramática libre de contexto probabilística — Una gramática libre de contexto probabilística (GLCP) es una gramática libre de contexto en la cual cada regla tiene asignada una probabilidad. La probabilidad de un análisis sintáctico es el producto de las probabilidades de cada una de las… …   Wikipedia Español

  • Analizador sintáctico — Un analizador sintáctico (en inglés parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación. El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.