# Programação dinâmica em linguagens

Reconhecimento CYK e construção de Kleene, com estados por intervalos e por intermediários permitidos.

Página: https://resumos.rgo.pt/cadeiras/da/linguagens-dinamica/

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

$$
B\in T[i,k]\quad\text{e}\quad C\in T[i+k,\ell-k].
$$

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

$$
S\to AB\mid AC,\qquad A\to a,\qquad B\to BA\mid b,\qquad C\to AA.
$$

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

| Comprimento | Segmento na posição 0 | Segmento na posição 1 | Segmento na posição 2 |
| --- | --- | --- | --- |
| 1 | `a`: $\{A\}$ | `b`: $\{B\}$ | `a`: $\{A\}$ |
| 2 | `ab`: $\{S\}$ | `ba`: $\{B\}$ | Não existe |
| 3 | `aba`: $\{S\}$ | Não existe | Não existe |

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.

**main.py**

```python
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")
```



**cyk_apoio.py**

```python
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$.

$$
R_{ij}^{(k)}=R_{ij}^{(k-1)}\mid R_{ik}^{(k-1)}\big(R_{kk}^{(k-1)}\big)^*R_{kj}^{(k-1)}.
$$

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

$$
R_{11}^{(0)}=\varepsilon\mid a,\quad R_{12}^{(0)}=b,\quad R_{21}^{(0)}=\varnothing,\quad R_{22}^{(0)}=\varepsilon\mid c.
$$

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](https://resumos.rgo.pt/cadeiras/da/caminhos-minimos/#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.

## Exercícios

A célula não conta árvores

Na gramática S→AA e A→AA|a, usa CYK para aceitar aaa e mostra duas árvores diferentes. Explica por que guardar apenas conjuntos não revela o número de árvores.

Pista

Cada símbolo a é gerado por A e aa também é gerado por A.

Mais uma pista

Na raiz S→AA, divide a|aa ou aa|a.

Solução

A linha de comprimento 1 contém A nas três posições. Cada segmento aa contém A por A→AA e S por S→AA. Para aaa, S surge com divisão 1+2 e com divisão 2+1. Uma árvore tem o A esquerdo a derivar diretamente a por A→a e o direito com dois filhos; a outra inverte esses tamanhos. O conjunto final contém S uma única vez, embora haja duas formas de o inserir. É preciso guardar divisões/produções ou contagens para ver essa multiplicidade.

Confere a tua resposta:

*   Mostrei as divisões 1+2 e 2+1.
*   Distingui conjunto de contagem de derivações.
*   Identifiquei duas árvores a partir de S.

Erros frequentes

Dois símbolos diferentes numa célula, por si só, não provam ambiguidade do símbolo inicial. Duas ordens de expansão da mesma árvore também não são duas árvores distintas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/linguagens-dinamica/#reconhecer-n%C3%A3o-%C3%A9-contar-deriva%C3%A7%C3%B5es)

Não esquecer repetições no estado intermédio

Um autómato tem inicial p, final r e transições p→q com a, q→q com b e q→r com c. Dá uma expressão regular e justifica a contribuição do ciclo quando q é permitido como intermediário.

Pista

O caminho chega a q com a e sai com c. Pode repetir o ciclo zero vezes.

Mais uma pista

Usa R\[p,q\] (R\[q,q\])\* R\[q,r\].

Solução

A expressão é ab_c. A construção permite chegar a q, dar zero ou mais voltas pelo ciclo de rótulo b e sair por c. Como R\[q,q\] inclui também o caminho vazio, (ε|b)_ simplifica-se para b\*. ac e abbbc são aceites; a ou abcabc não satisfazem esta sequência de transições.

Confere a tua resposta:

*   Obtive ab\*c.
*   Expliquei zero ou mais repetições.
*   Distingui ε e ausência de caminho.

Erros frequentes

Escrever abc obriga exatamente uma volta, e escrever ab+c obriga pelo menos uma e rejeita ac.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/linguagens-dinamica/#constru%C3%A7%C3%A3o-de-kleene)