O Pumping Lemma

Os limites das linguagens regulares.

• Introdução
• O Pumping Lemma
• Conclusão

Introdução

Nas secções anteriores avançou-se na resolução do Problema Principal de ALP — Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p\in A$ — com linguagens regulares.

As expressões regulares e os autómatos finitos (deterministas e não deterministas) são computáveis e eficientes mas ainda falta saber se são adequadas isto é, suficientemente expressivas para definir qualquer linguagem de programação.

As expressões algébricas, de uma forma ou outra, estão presentes em quase todas as linguagens de programação. Uma expressão algébrica é uma palavra como, por exemplo, 2 * (3 + 4) em que certas sub-palavras representam números (2, 3, 4), outras representam operações (+, *) e outras definem a estrutura da expressão ((, )).

A estrutura de uma expressão pode ser visualizada por uma árvore:

Árvore de uma Expressão Algébrica
Forma Alternativa

Naturalmente, pretende-se que no lugar de 2, 3 e 4 possam estar outras expressões algébricas e que as operações incluam, pelo menos, - e /. Conforme as expressões ficam mais complexas, maior a necessidade e a importância dos parêntesis.

A estrutura de um programa é semelhante à estrutura de uma expressão algébrica: Organiza-se como uma árvore com certos vértices "recursivos". Em vez de números e operações, nas árvores dos programas os vértices têm instruções, expressões, diretivas, etc.

if x > 2:
    a = double(x)
    for i in range(a):
        a = a + i
else:
    a = 0

Árvore de um Fragmento de Programa

Uma propriedade importante das expressões algébricas é que "os parêntesis têm de estar equilibrados". Descartando os números e as operações, restam apenas os parêntesis e obtêm-se palavras como (), ()(), (())()(()()), que são "válidas" enquanto que as palavras )(, ()), etc devem ser rejeitadas.

A "linguagem dos parêntesis equilibrados" é um excelente teste às linguagens regulares:

• Se for regular, as linguagens regulares são adequadas para definir as linguagens de programação. De facto, o LISP (ver a página na wikipédia) é uma linguagem de programação que usa parêntesis e pouco mais.
• Se não for regular, as linguagens regulares não permitem representar árvores de estruturas sintáticas como as expressões algébricas ou os programas python. Nesse caso será necessário tentar outra abordagem para as linguagens de programação.

O problema que se coloca agora é o seguinte: Como saber se uma dada linguagem é, ou não, regular?

Consideremos alguns exemplos (sobre o alfabeto $\Sigma =\left\{a,b\right\}$):

• $A=\left\{a^n:n\ge 0\right\}=L\left(a^{\ast }\right)$ é regular.
• $\overline{A}={\Sigma }^{\ast }\setminus A$ também é regular porque é o complementar de uma linguagem regular (na secção anterior viu-se como fazer a negação de um AFD).
• $B=\left\{b^n:n\ge 0\right\}=L\left(b^{\ast }\right)$ também é regular, assim como são $AB,B{A}^{\ast }(A\cup \overline{B})$, etc.

Neste casos o "exercício" é simples porque ou se encontra uma ER adequada ou são aplicados os resultados teóricos das secções anteriores para construir linguagens regulares.

Quanto a uma versão simples dos parêntesis equilibrados:

$$E=\left\{a^n{b}^n:n\ge 0\right\}.$$

As palavras de $E$ são $\lambda ,ab,aabb,aaabbb,\dots ,a^{91537}{b}^{91537},\dots$ Esta linguagem é regular?

De facto, como se prova que uma linguagem não é regular? O problema é o seguinte: Supondo que $A$ é uma linguagem regular. Como se prova que $A$ é regular? Basta encontrar uma ER (ou AFD ou AFND), $x$, adequada: $A=L(x)$.

Mas, se $A$ não for regular nenhuma ER é adequada. É preciso outro método para provar que $A$ não é regular.

Entra o Pumping Lemma.

O Pumping Lemma

Uma observação muito simples:

Um AFD com $n$ estados, quando processa uma palavra com mais do que $n$ símbolos, tem de "passar" mais do que uma vez em alguns estados, porque há mais símbolos do que estados.

Por exemplo, um AFD para $a^{\ast }$, ilustrado abaixo, tem exatamente dois estados.

AFD para $a^{\ast }$

Contando as entradas nos estados deste autómato:

Todas as palavras de comprimento $3$ entram mais do que uma vez em algum estado do autómato. Claramente, o mesmo acontece para palavras de comprimento $4,5,\dots$

Em geral, seja $p$ uma palavra que entra duas (ou mais) vezes no estado $i$. Então pode escrever-se $p=uvw$ em que:

• $u$ é o prefixo de $p$ que entra pela primeira vez em $i$.
• $v$ é uma sub-palavra de $p$ que parte de $i$ e entra de novo em $i$.
• $w$ é o restante sufixo de $p$.

Como (o caminho de) $v$ começa e termina em $i$, a sub-palavra $v$ pode ser indefinidamente repetida, inclusivamente eliminada, que o estado final da computação não se altera. Isto é, o estado final para $p=p_1=uvw$ é o mesmo que para $p_0=uw,p_2=uvvw,\dots ,p_{9375}=u{v}^{9375}w$.

Se $p$ for aceite, também são $p_0,p_1,p_2,\dots$. E, se $p$ for rejeitada, também são $p_0,p_1,p_2,\dots$

Formalmente:

Pumping Lemma. Seja $L$ uma linguagem regular e $k$ o número de estados de um AFD que a aceita.

Qualquer palavra $p\in L$ com $\left|p\right|>k$ pode ser escrita como $p=uvw$ em que:

1. $\left|uv\right|<k$.
2. $\left|v\right|>0$.
3. Para qualquer $n\ge 0$ também $u{v}^{n}w\in L$.

O Pumping Lemma é uma propriedade de todas as linguagens regulares. Dito de outra forma,

Se as conclusões do Pumping Lemma levarem a uma contradição é porque as hipóteses do Pumping Lemma não se verificam. Especificamente: a linguagem considerada não pode ser regular.

Revisitando a linguagem simplificada dos parêntesis equilibrados, $E=\left\{a^m{b}^m:m\ge 0\right\}$.

1. Supondo que $E$ é regular, também é aceite por um certo AFD.
2. Seja $k$ o número de estados desse AFD.
3. A palavra $p=a^k{b}^k\in E$.
4. Pelo Pumping Lemma, como $\left|p\right|>k$ então $p=uvw$ em que:
   1. $\left|uv\right|<k$. Portanto, $uv$ só tem $a$.
   2. $\left|v\right|>0$. Portanto $v$ tem pelo menos um $a$ e nenhum $b$.
   3. Para cada $n\ge 0$ também $p_n=u{v}^{n}w\in E$.

Em $p_n=u{v}^{n}w$, quando $v$ é repetido,o número de $a$ é alterado. Mas o número de $b$ continua a ser $k$. Portanto, quando $n\ne 1$, o número de $a$ deixa de ser igual ao número de $b$.

Isto é uma contradição. Por um lado, se $p_n=u{v}^{n}w\in E$ então tem o mesmo número de $a$ e de $b$ mas por outro, ao repetir $v$, $p_n$ fica com um número diferente de $a$ e de $b$.

Portanto a suposição inicial, de que a linguagem $E$ é regular, é falsa. A única conclusão possível é que $E$ não é uma linguagem regular.

O facto de $E$ não ser uma linguagem regular tem consequências profundas:

• Primeiro, encontrou-se uma linguagem que não é regular.
• Segundo, as linguagens regulares não são adequadas para definir linguagens de programação.

A incapacidade das linguagens regulares para definir a linguagem simplificada dos parêntesis equilibrados implica a incapacidade para definir as estruturas recursivas (como árvores) necessárias nas linguagens de programação.

Conclusão

O Pumping Lemma aplicado à linguagem $E=\left\{a^m{b}^m:m\ge 0\right\}$ mostra que as linguagens regulares não são adequadas para definir linguagens de programação.

Portanto, é necessária outra abordagem para resolver o Problema Principal de ALP — Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p\in A$ de forma computável, acessível e adequada.

Nem tudo está perdido. De facto, os conceitos introduzidos até aqui, as ER, os AFD e os AFND, vão continuar presentes no resto do curso e nas suas aplicações. O que muda é a importância que têm: Perdem o título de "candidato preferido" e passam a "contribuição necessária".

O próximo capítulo define certas gramáticas formais que, como vai ser mostrado, generalizam as linguagens regulares e estão associadas aos autómatos de pilha, uma forma simples de autómato com memória ilimitada.