Gramáticas livres de contexto

A regra $S\to aSb$ acrescenta um $a$ à esquerda e um $b$ à direita, deixando $S$ no meio para repetir a operação. Com uma regra de paragem $S\to\varepsilon$, obtemos $ab$, $aabb$ e blocos maiores com as mesmas contagens.

Uma gramática livre de contexto, CFG, usa regras para substituir variáveis como $S$ por sequências. Os terminais, aqui $a$ e $b$, ficam na palavra final. A substituição de $S$ não depende dos símbolos à sua volta.

Definição e derivações

Uma gramática livre de contexto, CFG, é $G=(V,\Sigma,P,S)$, onde $V$ é um conjunto finito de variáveis, $\Sigma$ é o alfabeto de terminais, $V\cap\Sigma=\emptyset$, $P$ é o conjunto finito de produções e $S\in V$ é a variável inicial.

Cada produção tem forma $A\to\alpha$, com uma única variável $A$ à esquerda e $\alpha\in(V\cup\Sigma)^*$ à direita. A palavra vazia pode aparecer à direita. Chama-se livre de contexto porque podes substituir $A$ por $\alpha$ independentemente dos símbolos à sua volta.

Escreve $xAy\Rightarrow x\alpha y$ para um passo de derivação e $\Rightarrow^*$ para zero ou mais passos. Uma forma sentencial é uma sequência derivável de $S$, que ainda pode conter variáveis e terminais. A linguagem contém só resultados inteiramente terminais:

Na gramática $S\to aSb\mid\varepsilon$:

$aaSbb$ ainda não é uma palavra da linguagem, porque contém $S$. Se queres excluir $\varepsilon$, podes usar $S\to aSb\mid ab$.

Para uma apresentação em vídeo de linguagens e gramáticas livres de contexto, tens Rodrigo Dias:

Linguagens e Gramáticas Independentes de ContextoCarregar vídeo do YouTube

Abrir no YouTube

Construir uma gramática e provar a linguagem

Para $L=\{a^nb^{2n}\mid n\ge0\}$, a produção recursiva deve acrescentar um $a$ e dois $b$:

Provar $L(G)=L$ exige duas inclusões.

A gramática não gera palavras extra. Faz indução no número de aplicações da produção recursiva. Sem aplicações, produz $\varepsilon=a^0b^0$. Se o meio gera $a^nb^{2n}$, então $aSbb$ gera $a^{n+1}b^{2n+2}$, mantendo a ordem e a proporção.

A gramática gera todas as palavras pretendidas. Para qualquer $n\ge0$, aplica $S\to aSbb$ exatamente $n$ vezes, obtendo $a^nSb^{2n}$, e termina com $S\to\varepsilon$.

Separar blocos e desigualdades

Para $\{a^nb^m\mid n\ge m\ge0\}$, usa

As primeiras $m$ aplicações emparelham um $a$ com um $b$. Depois, $A$ acrescenta $n-m$ letras $a$. Assim, $S\Rightarrow^*a^mAb^m\Rightarrow^*a^nb^m$. Para exigir $n>m$, troca a base de $A$ por $a$: $A\to aA\mid a$.

Para palíndromos binários de qualquer comprimento, uma gramática é $S\to0S0\mid1S1\mid0\mid1\mid\varepsilon$. As bases $0,1$ geram o centro de palavras ímpares; $\varepsilon$ gera as pares. Omitir essas bases muda a linguagem.

Igualdade de contagens em qualquer ordem

Para palavras sobre $\{a,b\}$ com o mesmo número de $a$ e de $b$, usa

A regra $SS$ junta dois blocos equilibrados. As regras $aSb$ e $bSa$ envolvem um par equilibrado à volta de outro bloco equilibrado. As bases cobrem os pares de comprimento 2 e a palavra vazia.

Para provar que só gera palavras equilibradas, faz indução na árvore de derivação. A base vazia está equilibrada; envolver uma palavra equilibrada acrescenta um símbolo de cada tipo, e $SS$ soma duas diferenças nulas.

Para a outra inclusão, usa indução no comprimento de $w$ equilibrada não vazia:

1. Se $w$ começa e termina em símbolos diferentes, escreve $w=aub$ ou $w=bua$ com $u$ equilibrada e aplica $aSb$ ou $bSa$.
2. Se começa e termina no mesmo símbolo, a diferença entre contagens vale $1$ ou $-1$ depois da primeira letra e tem o sinal oposto antes da última. Como varia uma unidade por letra, anula-se numa posição interior e $w$ parte-se em dois blocos equilibrados não vazios; aplica-se $SS$.

Para $abba$:

Desigualdade com três blocos

Para $\{a^ib^jc^k \mid i+j \ge k,\ i,j,k \ge 0\}$, gera primeiro os $a$, depois os $b$, e emparelha cada $c$ com um $a$ ou $b$ anterior, sem misturar a ordem dos blocos. Uma gramática:

Cada $aSc$ acrescenta um $a$ à esquerda e um $c$ à direita, enquanto cada $aS$ acrescenta um $a$ sem $c$. Depois de chegar a $B$, cada $bBc$ acrescenta um $b$ e um $c$, e cada $bB$ acrescenta um $b$ sem $c$.

Antes de mudar para $B$, a forma sentencial é $a^*Sc^*$; depois é $a^*b^*Bc^*$, e ao eliminar $B$ fica $a^*b^*c^*$. Se $S \Rightarrow^* a^pBc^q$ então $p \ge q$, e se $B \Rightarrow^* b^rc^s$ então $r \ge s$.

Logo a palavra final é $a^pb^rc^{q+s}$ com $p+r \ge q+s$. Isto prova que só gera palavras com $i+j \ge k$.

Para a outra inclusão, seja $i+j \ge k$. Escolhe quantos $c$ emparelhar com $a$ e quantos com $b$:

• $q=\min(i,k)$ pares $a/c$ e $s=k-q$ pares $b/c$. Então $q \le i$ e $s \le j$.
• Gera $i-q$ letras $a$ com $aS$, depois $q$ pares com $aSc$, depois $j-s$ letras $b$ com $bB$, depois $s$ pares com $bBc$.

Para $aabbbc$ temos $i=2$, $j=3$, $k=1$, logo $q=1$ e $s=0$. Uma derivação:

Os dois primeiros passos geram o excedente $a$ e o par $a/c$. Os três passos seguintes geram os três $b$ sem $c$. O último passo aplica $B \to \varepsilon$. Testa $abc$ com $q=1,s=0$ e $aabbcc$ com $q=2,s=0$; $abccc$ tem $i+j=2<3$ e nenhum par $(q,s)$ cumpre as desigualdades, por isso não é gerada.

Derivação à esquerda e à direita

Na derivação mais à esquerda, substitui sempre a variável mais à esquerda. Na derivação mais à direita, escolhe sempre a mais à direita. Nenhuma regra de produção muda, apenas a ordem de expansão.

Para $S\to AB$, $A\to aA\mid\varepsilon$, $B\to bB\mid\varepsilon$, a palavra $ab$ tem derivação mais à esquerda:

e mais à direita:

Estas duas ordens não demonstram ambiguidade. Ambas descrevem a mesma estrutura: $A$ gera $a$ e $B$ gera $b$.

Árvores sintáticas e ambiguidade

Numa árvore sintática, a raiz é $S$. Um nó $A$ com filhos $X_1,\ldots,X_k$ usa a produção $A\to X_1\cdots X_k$. As folhas lidas da esquerda para a direita dão a palavra; uma folha $\varepsilon$ não acrescenta símbolo.

Uma gramática é ambígua se alguma palavra terminal tem duas árvores sintáticas distintas. Equivalentemente, essa palavra tem duas derivações mais à esquerda distintas, ou duas mais à direita distintas.

A gramática $E\to E+E\mid E*E\mid a$ é ambígua. A palavra $a+a*a$ pode separar-se na raiz pelo $+$ ou pelo $*$:

Na primeira árvore, a raiz soma $a$ com $(a*a)$; na segunda, multiplica $(a+a)$ por $a$. As duas derivações mais à esquerda começam por regras diferentes:

Uma testemunha basta para provar ambiguidade. Para provar ausência de ambiguidade, precisas de um argumento para todas as palavras, não de falhar na procura de uma testemunha.

Precedência e associatividade

Para dar maior precedência a $*$ e associar os operadores à esquerda, separa níveis:

$F$ é um fator, um átomo ou uma expressão entre parênteses. $T$ junta fatores por multiplicação. $E$ junta termos por soma. Agora, o $+$ só surge no nível que pode separar somas, enquanto o produto fica dentro de $T$.

A recursão em $E\to E+T$ fica à esquerda, logo $a+a+a$ agrupa-se como $(a+a)+a$. Com $E\to T+E\mid T$, agrupar-se-ia à direita. Os parênteses em $F$ permitem alterar a precedência.

Compara as duas gramáticas do laboratório para $a+a+a$. A primeira expande a soma no ramo esquerdo, representando $(a+a)+a$; a segunda expande-a no ramo direito, representando $a+(a+a)$. Para $a+a*a$, ambas mantêm o produto dentro de $T$. Os testes de aceitação não distinguem estas estruturas, porque as duas gramáticas aceitam as mesmas expressões. Observa a árvore, além da resposta de aceitação.

O laboratório mostra uma árvore possível para a palavra. Essa árvore permite seguir as produções usadas; uma única árvore não prova que nenhuma outra existe.

Ambiguidade é uma propriedade da gramática. Uma gramática ambígua pode ter outra gramática não ambígua para a mesma linguagem. Algumas linguagens livres de contexto são inerentemente ambíguas, ou seja, todas as suas gramáticas são ambíguas. Não existe um algoritmo geral que decida a ambiguidade de qualquer CFG.

Classificar gramáticas

A hierarquia de Chomsky compara restrições sobre as produções. $A,B$ representam variáveis, $a$ um terminal, $u,v$ sequências de variáveis e terminais.

No tipo 3, podes decompor blocos de terminais com variáveis auxiliares até obter regras $A\to aB$, $A\to a$ e $A\to\varepsilon$ na versão à direita. As regras unitárias $A\to B$, possíveis quando $w=\varepsilon$, podem ser eliminadas.

Para o tipo 1, esta é a convenção de regras que não diminuem o comprimento. Se for preciso gerar $\varepsilon$, admite-se a exceção $S\to\varepsilon$, desde que $S$ não apareça em nenhum lado direito. No tipo 3, misturar regras lineares à esquerda com regras lineares à direita não prova regularidade.

Para classificar uma gramática, procura a classe mais restrita que todas as suas regras respeitam. Por exemplo, $S\to aSb\mid ab$ é de tipo 2: o lado esquerdo é uma variável, mas a variável do lado direito fica entre dois terminais, impedindo tipo 3.

Classificar a gramática não determina a menor classe da sua linguagem. $S\to SS\mid a$ não é linear, mas gera $\{a^n\mid n\ge1\}$, uma linguagem regular descrita por $aa^*$. As regras dadas são de tipo 2; outra gramática regular pode gerar a mesma linguagem.

De DFA para gramática

Toda a linguagem regular é livre de contexto. Para ver a construção, cria uma variável $A_q$ por estado de um DFA. Para cada $\delta(q,a)=r$, acrescenta $A_q\to aA_r$. Para cada final $f$, acrescenta $A_f\to\varepsilon$. A variável inicial é a do estado inicial.

Uma derivação acompanha um percurso da máquina, escrevendo a letra de cada transição. Só pode terminar quando chega a um final, por isso gera exatamente a linguagem do DFA.

A inclusão é estrita: $\{a^nb^n\mid n\ge0\}$ tem CFG, mas não tem DFA, pelo lema da repetição regular. As formas normais reorganizam CFG para facilitar algoritmos, sem aumentar o seu poder.