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 $Θ(n^3),$ donde n es la longitud de la cadena analizada. Esto hace a este 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.

## 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:

### 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 $R_k.$ 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 |

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

