Algoritmo CYK

O algoritmo Cocke-Younger-Kasami (CYK) determina se uma cadeia de caracteres pode ser gerada por uma determinada gramática livre de contexto e, se ela puder, como ela pode ser gerada. Esse processo é conhecido como a análise sintática da cadeia, no caso, ascendente. A versão padrão do algoritmo opera em gramáticas livres de contexto expressas através da Forma Normal de Chomsky (CNF). No pior caso, o algoritmo possui complexidade , em que é o comprimento da cadeia de caracteres e o tamanho da gramática CNF . Isso o torna um dos algoritmos mais eficientes no reconhecimento geral de linguagens livres de contexto. Entretanto, algoritmos mais rápidos e especializados existem para certos subconjuntos de linguagens livres de contexto.