Propriedades das livres de contexto

Em $S\to AB$, se $A$ puder desaparecer, $B$ também tem de poder gerar sozinho uma palavra a partir do início. Apagar $A\to\varepsilon$ sem acrescentar $S\to B$ perderia essa possibilidade.

A simplificação substitui o efeito das regras que elimina. Depois, a forma normal de Chomsky organiza as produções de CFG para calcular a pertença numa tabela.

Variáveis anuláveis, unitárias e inúteis

Uma variável é anulável se deriva $\varepsilon$. Começa nas produções $A\to\varepsilon$ e acrescenta uma variável quando alguma das suas produções contém apenas variáveis já anuláveis. Repete até estabilizar. Um terminal nunca é anulável.

Para eliminar produções vazias, cria todas as combinações de presença e ausência das ocorrências anuláveis em cada lado direito. Em $A\to BCB$, se $B$ for anulável e $C$ não for, surgem $BCB$, $CB$, $BC$ e $C$. As duas ocorrências de $B$ são escolhas independentes. Depois retira produções vazias, tratando separadamente a aceitação de $\varepsilon$.

Uma produção unitária tem forma $A\to B$, com duas variáveis. Calcula os pares $(A,B)$ em que $A$ chega a $B$ só com produções unitárias, incluindo $(A,A)$. Copia para $A$ todas as produções não unitárias de cada $B$ alcançado e retira as unitárias. Não basta apagar $A\to B$, porque perderias as palavras geradas através dela.

Uma variável é geradora se deriva alguma palavra terminal. Calcula primeiro as geradoras, a partir de regras só com terminais ou variáveis já geradoras. Retira as não geradoras e as regras que as usam. Depois calcula as variáveis alcançáveis a partir do início na gramática que ficou e retira as restantes.

Por exemplo, em $S\to AB\mid a$, $A\to b$, sem regras para $B$, $B$ não é geradora. Retira $S\to AB$ e, só depois, vês que $A$ ficou inacessível. O resultado é $S\to a$.

Uma ordem segura para a simplificação completa é: eliminar produções vazias, eliminar unitárias e eliminar símbolos inúteis, primeiro não geradores e depois inacessíveis. A eliminação de vazias pode criar unitárias, e as etapas podem tornar símbolos inúteis.

Simplificação acompanhada numa gramática

Considera a gramática

$$S\to AB\mid a,\quad A\to b\mid\varepsilon,\quad B\to C,\quad C\to cC\mid c,\quad D\to d.$$

1. Só $A$ é anulável. Em $S\to AB$, omitir $A$ cria $S\to B$. Retira depois $A\to\varepsilon$.
2. Agora há as unitárias $S\to B$ e $B\to C$. A cadeia chega de $S$ a $C$, pelo que copiamos $cC$ e $c$ para ambos $S$ e $B$, e retiramos as duas unitárias.
3. Todas as variáveis são geradoras, mas $D$ é inacessível a partir de $S$ e sai.

O resultado completo é:

$$S\to AB\mid a\mid cC\mid c,\quad A\to b,\quad B\to cC\mid c,\quad C\to cC\mid c.$$

$bc$ continua a derivar por $S\Rightarrow AB\Rightarrow bB\Rightarrow bc$. A palavra $c$, que antes dependia de apagar $A$, deriva agora diretamente por $S\Rightarrow c$. A linguagem mantém-se $(\varepsilon+b)cc^*+a$.

Intercalação de uma CFL com uma regular

Se $L$ é CFL e $R$ é regular, a intercalação $inter(L,R)$ é CFL. A construção usa um PDA $P$ por estado final para $L$ e um DFA $D$ para $R$:

1. Usa um fundo novo, que a simulação de $P$ não retira, para permitir ler letras de $R$ mesmo depois de a pilha simulada ficar vazia.
2. Constrói um PDA cujo estado é $(p,q)$: ao ler uma letra, escolhe avançar $P$ mantendo $q$, ou avançar $D$ mantendo $p$ e a pilha. Transições vazias de $P$ mantêm $q$.
3. Aceita quando $p$ é final em $P$, $q$ é final em $D$ e a entrada foi consumida.

Cada letra é atribuída a uma das duas palavras, preservando a ordem interna de cada uma. Isto generaliza a construção para intercalação regular/regular, onde dois DFA chegam; aqui a pilha de $P$ acompanha apenas as letras atribuídas a $L$.

Forma normal de Chomsky

Na forma normal de Chomsky, CNF, as produções têm forma

$$A\to BC\quad\text{ou}\quad A\to a.$$

Adota a extensão que permite $S_0\to\varepsilon$ se a linguagem contém a palavra vazia, desde que o início $S_0$ não apareça em nenhum lado direito. Uma regra $S_0\to S$ é unitária e não fica na CNF final desta convenção.

Depois da simplificação, substitui cada terminal em lados direitos de comprimento pelo menos dois por uma variável nova, como $T_a\to a$. Não alteres $A\to a$, que já está na forma certa.

Divide os lados direitos compridos: $A\to BCD$ torna-se $A\to BX$, $X\to CD$, com $X$ novo. Para quatro ou mais variáveis, continua a cadeia. Cada regra passa a ter duas variáveis ou um terminal.

Conversão completa

Parte de $S\to aSb\mid\varepsilon$. Introduz $A\to a$, $B\to b$, ficando $S\to ASB\mid\varepsilon$. O início $S$ é anulável e aparece à direita; cria um início novo $S_0$ para preservar $\varepsilon$.

Eliminando a ocorrência anulável de $S$ no meio, tens $S\to ASB\mid AB$. Copia estas regras para $S_0$ para eliminar $S_0\to S$, e conserva $S_0\to\varepsilon$. Finalmente, divide $ASB$ com $C\to SB$:

$$\begin{aligned} S_0&\to AC\mid AB\mid\varepsilon,\\ S&\to AC\mid AB,\\ C&\to SB,\\ A&\to a,\qquad B\to b. \end{aligned}$$

$S_0$ não aparece à direita. Para $aabb$, a derivação é $S_0\Rightarrow AC\Rightarrow aC\Rightarrow aSB\Rightarrow aABB\Rightarrow aaBB\Rightarrow aabB\Rightarrow aabb$. A base $AB$ dá um par, e $AC$ acrescenta outro par à volta.

CYK: decidir a pertença

O algoritmo CYK usa uma CFG em CNF e uma palavra não vazia $w=a_1\cdots a_n$. A célula $T[i,j]$ contém as variáveis que geram a subpalavra $a_i\cdots a_j$.

Na diagonal:

$$T[i,i]=\{A\mid A\to a_i\}.$$

Para intervalos maiores, tenta todos os cortes $k$ entre $i$ e $j$. Se $A\to BC$, $B\in T[i,k]$ e $C\in T[k+1,j]$, acrescenta $A$ a $T[i,j]$. Preenche por comprimento crescente, porque cada decisão depende de intervalos menores.

Com a CNF anterior e $aabb$, obténs a tabela abaixo por comprimento crescente. Os índices $[i,j]$ identificam as posições da subpalavra na entrada:

Intervalo e palavra	Variáveis
$[1,1]: a$	$\{A\}$
$[2,2]: a$	$\{A\}$
$[3,3]: b$	$\{B\}$
$[4,4]: b$	$\{B\}$
$[1,2]: aa$	$\emptyset$
$[2,3]: ab$	$\{S_0,S\}$
$[3,4]: bb$	$\emptyset$
$[1,3]: aab$	$\emptyset$
$[2,4]: abb$	$\{C\}$
$[1,4]: aabb$	$\{S_0,S\}$

Em $abb$, o corte $ab\mid b$ usa $C\to SB$. Em $aabb$, o corte $a\mid abb$ usa $S_0\to AC$. Como $S_0\in T[1,4]$, a palavra pertence à linguagem.

Não juntes todos os símbolos de uma linha sem respeitar o intervalo e o corte. $B$ no último $b$ só pode combinar com uma variável que gere a parte imediatamente anterior no mesmo intervalo.

Para gramática fixa, há $O(n^2)$ células e $O(n)$ cortes por célula, dando tempo $O(n^3)$ e espaço $O(n^2)$. Se a gramática variar, o custo inclui também o número de produções. Para $\varepsilon$, não crias uma tabela vazia: verifica diretamente se o início pode gerar a palavra vazia.

Propriedades de fecho

As livres de contexto são fechadas para união, concatenação, estrela e reverso. Para união, usa um início novo $S\to S_1\mid S_2$, após renomear variáveis para os conjuntos serem disjuntos. Para concatenação, usa $S\to S_1S_2$; para estrela, usa $S\to S_1S\mid\varepsilon$.

São também fechadas para interseção com uma regular. O produto entre PDA e DFA guarda ambos os estados, conservando a pilha do PDA. Uma transição vazia do PDA não altera o estado do DFA; uma letra lida atualiza ambos. Aceita quando as duas condições finais se verificam após consumir a entrada.

Não são fechadas para interseção entre duas CFL. Considera:

$$L_1=\{a^nb^nc^m\mid n,m\ge0\},\qquad L_2=\{a^mb^nc^n\mid n,m\ge0\}.$$

Cada uma compara apenas dois blocos, mas a interseção é $\{a^nb^nc^n\mid n\ge0\}$, que não é livre de contexto. Também não há fecho geral para complemento: se houvesse, as leis de De Morgan e o fecho para união dariam fecho para interseção. A diferença geral falha pela mesma razão, pois $\Sigma^*\setminus L$ é um caso de diferença.

Lema da repetição para CFL

Se $L$ é livre de contexto, existe $p\ge1$ tal que toda a palavra $s\in L$, $|s|\ge p$, admite $s=uvwxy$ com:

$$|vwx|\le p,\qquad |vx|\ge1,\qquad \forall i\ge0,\ uv^iwx^iy\in L.$$

A condição $|vx|\ge1$ permite que uma das partes seja vazia, mas não ambas; bombeia $v$ e $x$ com o mesmo expoente, enquanto $w$ fica uma única vez. Ao contrário do lema regular, a zona limitada não tem de estar no princípio da palavra.

Uma árvore sintática suficientemente alta repete uma variável num caminho. Podes retirar a parte entre as duas ocorrências, ou repeti-la. Essa parte acrescenta $v$ de um lado da subárvore interior e $x$ do outro. Uma CNF permite limitar o tamanho da zona que contém a repetição.

Provar que aⁿbⁿcⁿ não é CFL

Supõe que $L=\{a^nb^nc^n\mid n\ge0\}$ é CFL e seja $p$ o comprimento do lema. Escolhe $s=a^pb^pc^p$. Considera qualquer decomposição válida.

Como $|vwx|\le p$, essa zona não pode conter ao mesmo tempo um $a$ e um $c$: teria de incluir todo o bloco de $p$ letras $b$, além dos dois extremos. Logo, a zona deixa intacto pelo menos um dos tipos de símbolo extremos.

Com $i=0$, retiras $v$ e $x$. Retiras pelo menos um símbolo, pois $|vx|\ge1$, enquanto o tipo que não aparece na zona mantém as suas $p$ ocorrências. As três contagens já não são iguais. Portanto, $uwy\notin L$, contradizendo o lema.

Não escolhes uma decomposição conveniente. A limitação da zona cobre todas as decomposições. Como no lema regular, satisfazer o lema não prova pertença à classe.

A palavra escolhida pode admitir uma repetição

Estar na linguagem e ter comprimento suficiente são condições necessárias para uma testemunha, mas não chegam para a prova negativa. Considera

$$K=\{a^nb^nz\mid n\ge0,\ z\in\{a,b\}^n\}.$$

O último bloco tem comprimento $n$, mas as suas letras são livres. Não exige três contagens iguais de símbolos diferentes.

Supondo $K$ CFL, recebe o comprimento $p$ do lema. Podemos aumentá-lo para $p\ge3$, pois a condição continua válida com um limite maior. A candidata $a^pb^{2p}$ pertence a $K$, escolhendo $z=b^p$. Porém, admite um corte que o adversário pode usar para escapar à contradição:

$$u=a^{p-1},\quad v=a,\quad w=\varepsilon,\quad x=bb,\quad y=b^{2p-2}.$$

O corte tem $|vwx|=3\le p$ e $|vx|=3>0$. Para qualquer expoente $i\ge0$, a palavra bombeada é

$$a^{p-1+i}b^{2(p-1+i)}.$$

Continua em $K$, com $n=p-1+i$ e bloco final $z=b^n$. Encontrámos um corte que impede a contradição com esta candidata. Isto não prova que $K$ seja CFL; mostra que precisamos de escolher outra palavra.

Separar a zona curta dos extremos

Escolhe agora $s=a^{2p}b^{2p}a^{2p}\in K$. A zona $vwx$ tem comprimento no máximo $p$ e não pode tocar nos dois blocos de $a$, pois teria de atravessar os $2p$ símbolos $b$. É esta a testemunha que funciona: força o adversário a retirar símbolos de uma região que desequilibra sempre a palavra.

Bombeia com $i=0$. Seja $\alpha$ a quantidade retirada do primeiro bloco, $\beta$ do bloco de $b$ e $\gamma$ do último. A palavra fica $a^jb^ka^\ell$, com

$$j=2p-\alpha,\quad k=2p-\beta,\quad\ell=2p-\gamma.$$

Todos os blocos continuam não vazios, porque retiramos no máximo $p$ símbolos. Para pertencer a $K$, a primeira mudança de $a$ para $b$ fixa $n=j$. É preciso ter $k\ge j$ letras $b$ para o bloco obrigatório. O que sobra, $b^{k-j}a^\ell$, deve ter comprimento $j$, portanto $k+\ell=2j$.

Estas condições excluem todos os cortes:

Zona que contém as partes retiradas	Condição que falha
Não retira do primeiro bloco, $\alpha=0$	$\beta+\gamma>0$ dá $k+\ell<4p=2j$.
Retira do primeiro bloco, $\alpha>0$	O último fica intacto, $\gamma=0$. A igualdade exigiria $\beta=2\alpha$, mas $k\ge j$ exigiria $\beta\le\alpha$. São incompatíveis.

Como $v,x$ não são ambos vazios, algum símbolo sai. Em qualquer decomposição válida, a palavra bombeada deixa $K$. Esta contradição prova que $K$ não é CFL. A prova usa o significado do último bloco, não uma falsa exigência de que contenha só $a$.

O que se pode decidir sobre CFG

A pertença é decidível por CYK. O vazio é decidível verificando se o início é gerador. Já não há algoritmos gerais que decidam equivalência de duas CFG, universalidade de uma CFG ou ambiguidade de uma CFG.

Isto não impede resolver exemplos particulares com um argumento. Dizer que um problema é indecidível significa que não existe um algoritmo que termine e responda corretamente a todas as entradas desse problema.