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.
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.
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.
Los pesos o probabilidades serán guardados en la tabla P en vez de los valores booleanos.