Programação dinâmica em linguagens

As regras $S\to AB$, $A\to a$ e $B\to b$ geram ab: começamos no símbolo inicial $S$ e substituímos os símbolos auxiliares até restarem terminais. Para palavras maiores, testar todas as derivações seria impraticável. O CYK combina os símbolos que geram segmentos menores numa tabela por intervalos e responde sem enumerar árvores.

A construção de Kleene também guarda resultados parciais, mas descreve caminhos de um autómato com expressões regulares. Os ciclos exigem representar repetições com estrela, em vez de enumerar todos os caminhos possíveis.

CYK e forma normal de Chomsky

CYK decide se uma palavra pertence à linguagem de uma gramática independente de contexto, ou seja, ao conjunto das palavras obtidas por substituições sucessivas a partir do símbolo inicial até restarem terminais. Usa produções da forma $A\to BC$ ou $A\to a$, com não-terminais $A,B,C$ e terminal $a$. Estas regras são a forma normal de Chomsky para palavras não vazias. Pode admitir-se ainda $S\to\varepsilon$, desde que o inicial $S$ não apareça em lados direitos; a palavra vazia é então tratada separadamente. Regras unitárias, como $A\to B$, ou regras com três não-terminais exigem conversão antes deste algoritmo.

Define $T[i,\ell]$ como o conjunto de não-terminais que geram o segmento da palavra que começa no índice $i$ e tem comprimento $\ell$. Para comprimento 1, inclui $A$ quando há produção $A\to w[i]$.

Para $\ell\ge2$, experimenta cada divisão $k$ entre 1 e $\ell-1$. Inclui $A$ em $T[i,\ell]$ quando existe $A\to BC$ com

Preenche comprimentos por ordem crescente. O símbolo inicial em $T[0,n]$ significa aceitação. A regra combina os dois filhos da raiz de uma árvore de derivação; por indução no comprimento, os conjuntos representam exatamente os segmentos deriváveis.

Uma tabela pequena

Considera a gramática

Para aba, a linha de comprimento 1 é $\{A\},\{B\},\{A\}$. Para comprimento 2:

• ab contém $S$, porque $S\to AB$.
• ba contém $B$, porque $B\to BA$.

Para comprimento 3, dividir a | ba permite $S\to AB$. A divisão ab | a não encontra produção com os pares disponíveis $S,A$. O conjunto final é $\{S\}$; a palavra é aceite. Uma derivação é $S\Rightarrow AB\Rightarrow aB\Rightarrow aBA\Rightarrow abA\Rightarrow aba$.

As posições sem segmento não são conjuntos vazios: estão fora da tabela triangular. Para abb, o segmento final bb tem conjunto vazio, pois nenhuma produção combina B com B. A palavra inteira também fica sem não-terminais e é rejeitada.

O código mantém visível o preenchimento da tabela e a decisão de aceitação. mostrar_tabela_cyk apenas escreve os conjuntos por comprimento; podes consultar essa função no código de apoio. Troca a palavra de entrada por abb e compara as tabelas.

from cyk_apoio import mostrar_tabela_cyk

word = input().strip()
if not word or len(word) > 40 or any(c not in "ab" for c in word):
    print("entrada invalida")
else:
    terminal = {"a": {"A"}, "b": {"B"}}
    binary = [("S", "A", "B"), ("S", "A", "C"),
              ("B", "B", "A"), ("C", "A", "A")]
    n = len(word)
    table = {}
    for i, char in enumerate(word):
        table[i, 1] = set(terminal[char])
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            found = set()
            for split in range(1, length):
                for parent, left, right in binary:
                    if left in table[i, split] and right in table[i + split, length - split]:
                        found.add(parent)
            table[i, length] = found
    mostrar_tabela_cyk(table, n)
    print("aceite" if "S" in table[0, n] else "rejeitada")

def mostrar_tabela_cyk(table, n):
    for length in range(1, n + 1):
        cells = ["{" + ",".join(sorted(table[i, length])) + "}"
                 for i in range(n - length + 1)]
        print(f"comprimento {length}: " + " ".join(cells))

A saída lista as linhas de comprimento 1, 2 e 3 e termina com aceite. abb é rejeitada. O programa aceita apenas palavras não vazias de a e b, até 40 símbolos, e usa exatamente esta gramática.

Para uma gramática fixa, há $O(n^2)$ células e $O(n)$ divisões por célula, dando $O(n^3)$ tempo. Se a gramática fizer parte da entrada e percorremos as suas produções binárias, o limite é $O(n^3|P|)$. Os conjuntos usam $O(n^2|N|)$ espaço na representação direta, onde $N$ é o conjunto de não-terminais.

Reconhecer não é contar derivações

Ter dois não-terminais numa célula não prova ambiguidade. Pode apenas significar que dois símbolos diferentes geram o mesmo segmento. A gramática é ambígua se alguma palavra tiver duas árvores de derivação distintas a partir do símbolo inicial.

Por exemplo, $S\to AA$, $A\to AA\mid a$ gera aaa com as divisões a | aa e aa | a na raiz. Para reconstruir uma árvore, guarda uma produção e uma divisão por inclusão. Para investigar ambiguidade desta palavra, guarda todas as alternativas ou conta árvores por estado. Apenas os conjuntos de CYK não mostram quantas alternativas levaram ao mesmo não-terminal.

Operações regulares antes de Kleene

Uma expressão regular combina linguagens com três operações. A união $R\mid S$ aceita palavras de qualquer das partes. A concatenação $RS$ cola uma palavra de $R$ com outra de $S$. A estrela $R^*$ repete $R$ zero ou mais vezes. O símbolo $\varnothing$ representa o conjunto vazio; $\varepsilon$ representa a palavra vazia de comprimento zero. Assim $(\varepsilon\mid a)$ aceita vazio ou $a$, e $(\varepsilon\mid a)^*$ aceita qualquer sequência de $a$, ou seja $a^*$.

Construção de Kleene

Um autómato finito pode ter ciclos, portanto enumerar os seus caminhos não termina. A construção de Kleene descreve os caminhos através de expressões regulares, permitindo progressivamente mais estados intermédios.

Num autómato com estados $1,\ldots,n$, define $R_{ij}^{(k)}$ como a expressão regular das palavras que levam de $i$ a $j$ usando apenas $1,\ldots,k$ como estados intermédios. Inicialmente, $R_{ij}^{(0)}$ é a união dos rótulos das transições diretas; inclui $\varepsilon$ se $i=j$. Se não há transição nem caminho vazio, usa $\varnothing$.

A primeira alternativa não passa por $k$. A segunda chega a $k$, repete zero ou mais voltas de $k$ para $k$ e sai para $j$. O asterisco é necessário: sem ele, só permitiríamos uma visita a $k$.

A expressão final é a união de $R_{sf}^{(n)}$ para todos os estados finais $f$, onde $s$ é o inicial. Se o inicial também for final, a palavra vazia pertence à linguagem.

Exemplo com dois estados

Se o estado 1 é inicial, 2 é final, há ciclo $1\xrightarrow{a}1$, transição $1\xrightarrow{b}2$ e ciclo $2\xrightarrow{c}2$, os estados iniciais são

Permitir o intermediário 1 dá $R_{12}^{(1)}=b\mid(\varepsilon\mid a)(\varepsilon\mid a)^*b$, equivalente a $a^*b$. Permitir o intermediário 2 acrescenta repetições de $c$, dando uma expressão equivalente a $a^*bc^*$.

A palavra aaabcc pertence à linguagem; aaacc não, porque falta a transição $b$ que chega ao estado final. $\varnothing$ e $\varepsilon$ são distintos: o primeiro não gera palavra nenhuma, o segundo gera uma palavra de comprimento zero.

Custo e semelhança com Floyd-Warshall

Há $n$ etapas e $n^2$ pares, logo $O(n^3)$ combinações de expressões. Isso não garante que o texto expandido da expressão final tenha tamanho polinomial. Copiar expressões inteiras pode provocar crescimento muito grande; partilhar subexpressões numa representação em grafo evita cópias, mas expandi-las para uma string pode continuar caro.

O índice exterior $k$ tem o mesmo papel que em Floyd-Warshall. Ali combinamos custo por mínimo e soma; aqui combinamos linguagens por união, concatenação e fecho. Esta semelhança vem do significado dos estados, não de coincidência de código. Para uma implementação direta de Kleene, usa os valores da etapa anterior ou uma atualização cuidadosamente justificada para não misturar níveis.