# 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 $\Theta (n^{3}\cdot |G|)$, em que $n$ é o comprimento da cadeia de caracteres e $|G|$ o tamanho da gramática CNF $G$. 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.

## Algoritmo
### Em pseudocódigo

Segue abaixo uma definição do algoritmo em pseudocódigo:

### Em prosa

Em termos informais, esse algoritmo considera cada possível subsequência da sequência de palavras e conjuntos $P[i,j,k]$ ser verdadeira se a subsequência de palavras de tamanho $i$ começando de $j$ poder ser gerada de $R_{k}$. Após avaliar as subsequências de tamanho 1, avalia as de tamanho 2, e assim sucessivamente. Para subsequências de tamanho 2 ou maior, considera cada possível partição da subsequência em duas partes e verifica se existe uma produção $P\to Q\;R$ tal que $Q$ coincide com a primeira parte e $R$ coincide com a segunda parte. Caso sim, ele grava $P$ como coincidindo com a subsequência inteira. Quando esse processo é terminado, a sentença é reconhecida pela gramática se a subsequência contendo a sentença inteira coincide a partir do símbolo inicial.

## Exemplo

Esse é um exemplo de gramática:
    ${\begin{array}{lcl}{\mathit {S}}&\to &{\mathit {NP}}\;{\mathit {VP}}\\{\mathit {VP}}&\to &{\mathit {VP}}\;{\mathit {PP}}\\{\mathit {VP}}&\to &{\mathit {V}}\;{\mathit {NP}}\\{\mathit {VP}}&\to &{\textit {come}}\\{\mathit {PP}}&\to &{\mathit {P}}\;{\mathit {NP}}\\{\mathit {NP}}&\to &{\mathit {Det}}\;{\mathit {N}}\\{\mathit {NP}}&\to &{\textit {ela}}\\{\mathit {V}}&\to &{\textit {come}}\\{\mathit {P}}&\to &{\textit {com}}\\{\mathit {N}}&\to &{\textit {peixe}}\\{\mathit {N}}&\to &{\textit {garfo}}\\{\mathit {Det}}&\to &{\textit {um}}\end{array}}$
A sentença ela come um peixe com um garfo é analisada utilizando o algoritmo CYK. Na tabela a seguir, em $P[i,j,k]$, $i$ é o número da linha (começando inferiormente em 1) e $j$ é o número da coluna (começando pela esquerda em 1).
Tabela CYK :
| S |
| | VP |
| S | | | |
| | VP | | | PP |
| S | | NP | | | NP |
| NP | V, VP | Det. | N | P | Det | N |
| ela | come | um | peixe | com | um | garfo |
A tabela CYK para P é representada aqui como uma matriz bidimensional M contendo um conjunto de símbolos não terminais, tais que R$_k$ está em M[i,j] se e somente se P[i,j,k]. No exemplo acima, como o símbolo inicial S está em M[7,1], a sentença pode ser gerada pela gramática.

## Extensões
### Gerando uma árvore sintática

O algoritmo acima é somente um reconhecedor que somente determina se uma sentença está na linguagem. No entanto, é trivial estender o algoritmo para determinar não somente se uma sentença pertence a uma linguagem, mas também a árvore de análise sintática, armazenando-se os nós como elementos do vetor ao invés de somente valores booleanos. O nó é conectado aos elementos do vetor que foram usados para produzi-lo para assim produzir a estrutura de árvore. Apenas um nó em cada elemento do vetor é necessário se apenas uma árvore sintática será produzida. No entanto, se todas as árvores sintáticas de uma sentença ambígua precisarem ser mantidas, é necessário guardar no elemento do vetor uma lista de todos os caminhos que o nó correspondente pode ser obtido no processo de análise sintática. Isso é as vezes feito com uma segunda tabela B[n,n,r] de apontadores. O resultado final, então, é uma floresta de árvores possíveis, onde partes comuns de árvores são consideradas entre as várias análises. Essa floresta de árvores pode ser convenientemente lida como uma gramática ambígua gerando apenas a sentença analisada, mas com mesma ambiguidade que a gramática original, e as mesmas árvores sintáticas até um simples renomeamento de não terminais, como mostrado por Lang (1994).

### Analisando gramáticas livre de contexto que não estão na CNF

Como mostrado por Lange & Leiß (2009), a desvantagem de todas as transformações conhecidas para a Forma Normal de Chomsky é que elas podem conduzir a um inchaço indesejado no tamanho da gramática. O tamanho da gramática é a soma dos tamanhos de suas regras de produção, onde o tamanho de uma regra é um mais o tamanho de seu lado direito. Usando $g$ para denotar o tamanho da gramática original, o aumento de tamanho no pior caso pode variar de $g^{2}$ até $g^{2g}$, dependendo do algoritmo de transformação utilizado. Para uso didático, Lange e Leiss trazem uma generalização leve do algoritmo CYK, sem comprometer a eficiência do algoritmo, claridade ou simplicidade de provas (Lange & Leiß 2009).

### Analisando gramáticas livre de contexto com pesos

Também é possível estender o algoritmo CK para analisar cadeias de caracteres usando gramáticas livre de contexto estocásticas e com pesos. Os pesos (probabilidades) são armazenados na tabela P ao invés de booleanos, então P[i,j,A] conterá o peso mínimo (maior probabilidade) que a substring de i a j pode ser derivada de A. Extensões do algoritmo permitem análises de uma cadeia de caracteres ser enumerada do menor para o maior peso (da maior para a menor probabilidade).

### Algoritmo de Valiant

O pior caso do CYK é de complexidade $\Theta (n^{3}\cdot |G|)$, onde n é o tamanho da cadeia analisada e |G| o tamanho da gramática CNF G. Isso significa que é um dos algoritmos mais eficientes para reconhecer gramáticas livres de contexto na prática. Valiant (1975) fez uma extensão ao algoritmo CYK. O algoritmo dele computa a mesma tabela que o algoritmo CYK, mas ele mostrou que algoritmos de multiplicação eficiente de matrizes com entradas 0-1 podem ser utilizados para realizar essa computação.
Utilizando o Algoritmo de Coppersmith-Winograd para multiplicar essas matrizes, isso dá uma complexidade no pior caso de $O(n^{2.38}\cdot |G|)$. No entanto, o termo constante escondido pela notação assintótica é tão grande que o Algoritmo Coppersmith-Winograd é apenas válido para matrizes que são grandes demais para manusear nos computadores dos dias atuais (Knuth 1997), e essa abordagem requer subtração e então é apenas válida para reconhecimento. A dependência de uma multiplicação de matrizes eficiente não pode ser evitada: Lee (2002) provou que qualquer analisador para gramáticas livre-de-contexto que executem em tempo $O(n^{3-\varepsilon }\cdot |G|)$ pode ser efetivamente convertido em um algoritmo computando o produto de matrizes $n\times n$ com entradas 0-1 em tempo $O(n^{3-\varepsilon /3})$.