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
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 contiene 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 |
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).
