Lema do bombeamento para linguagens livres de contexto

O lema do bombeamento para linguagens livres de contexto, também conhecido como o lema de Bar-Hillel, é um lema que dá uma propriedade compartilhada por todas as linguagens livres de contexto.

Enunciado formal

Se uma linguagem L é livre de contexto, então existe algum inteiro p ≥ 1 tal que qualquer sequência de caracteres s em L com |s| ≥ p (onde p é o comprimento do bombeamento) pode ser escrita como

s = uvxyz

com sub cadeias u, v, x, y e z, tal que |vxy| ≤ p, |vy| ≥ 1, e

uv^nxy^nz está em L para todo inteiro n ≥ 0.

Expressão formal

O lema do bombeamento para linguagens livres de contexto (chamado apenas "lema do bombeamento" de agora em diante) descreve uma propriedade que todas as linguagens livres de contexto garantidamente possuem.

A propriedade é uma propriedade de todas as cadeias na linguagem que são de comprimento pelo menos p, onde p é uma constante chamada comprimento do bombeamento -- que varia entre as linguagens livres de contexto.

Seja s uma cadeia de comprimento pelo menos p que está na linguagem.

O lema do bombeamento diz que s pode ser dividida em cinco sub cadeias, ${\displaystyle s=uvxyz}$, onde vy não é vazia e o comprimento de vxy é no máximo p, tal que repetindo v e y qualquer (e o mesmo) número de vezes em s produz uma cadeia que ainda está na linguagem (é possível e frequentemente útil repetir zero vezes, o que remove v e y da cadeia). Este processo de "bombear para cima" cópias adicionais de v e y é o que dá nome ao lema do bombeamento.

Observe que linguagens finitas (que são regulares e portanto livres de contexto) obedecem ao lema do bombeamento trivialmente por ter p igual ao comprimento da maior cadeia em L mais um. Como não existem cadeias desse comprimento o lema do bombeamento não é violado.

O lema do bombeamento é frequentemente usado para provar que uma determinada linguagem não é livre de contexto, mostrando que para todo p podemos encontrar alguma cadeia s de comprimento pelo menos p na linguagem que não possua as propriedades citadas acima, ou seja, que não possa ser "bombeada" sem produzir algumas cadeias que não estão na linguagem.

Uso do lema

O lema do bombeamento para linguagens livres de contexto pode ser usado para mostrar que certas linguagens não são livres de contexto.

Por exemplo, podemos mostrar que a linguagem ${\displaystyle L=\lbrace a^{i}b^{i}c^{i}|i>0\rbrace }$ não é livre de contexto usando o lema do bombeamento em uma prova por contradição. Primeiro, suponha que ${\displaystyle L}$ é livre de contexto. Pelo lema do bombeamento, existe um inteiro ${\displaystyle p}$ que é o comprimento de bombeamento da linguagem ${\displaystyle L}$. Considere a cadeia ${\displaystyle s=a^{p}b^{p}c^{p}}$ em ${\displaystyle L}$. O lema do bombeamento nos diz que ${\displaystyle s}$ pode ser escrita na forma ${\displaystyle s=uvxyz}$, onde ${\displaystyle u,v,x,y}$, e ${\displaystyle z}$ são subcadeias, tal que ${\displaystyle |vxy|\leq p}$, ${\displaystyle |vy|\geq 1}$, e ${\displaystyle uv^{i}xy^{i}z}$ está em ${\displaystyle L}$ para todo inteiro ${\displaystyle i\geq 0}$. Pela nossa escolha de ${\displaystyle s}$ e o fato de que ${\displaystyle |vxy|\leq p}$, é facilmente visto que a subcadeia ${\displaystyle vxy}$ não pode conter mais de duas letras distintas. Ou seja, temos uma das cinco possibilidades para ${\displaystyle vxy}$:

1. ${\displaystyle vxy=a^{j}}$ para algum ${\displaystyle j\leq p}$.
2. ${\displaystyle vxy=a^{j}b^{k}}$ para algum ${\displaystyle j}$ e ${\displaystyle k}$ com ${\displaystyle j+k\leq p}$.
3. ${\displaystyle vxy=b^{j}}$ para algum ${\displaystyle j\leq p}$.
4. ${\displaystyle vxy=b^{j}c^{k}}$ para algum ${\displaystyle j}$ e ${\displaystyle k}$ com ${\displaystyle j+k\leq p}$.
5. ${\displaystyle vxy=c^{j}}$ para algum ${\displaystyle j\leq p}$.

Para cada caso, é fácil verificar que ${\displaystyle uv^{i}xy^{i}z}$ não contém quantidades iguais de cada letra para qualquer ${\displaystyle i\neq 1}$. Assim, ${\displaystyle uv^{2}xy^{2}z}$ não tem a forma ${\displaystyle a^{i}b^{i}c^{i}}$. Isto contradiz a definição de ${\displaystyle L}$. Portanto, nossa hipótese inicial de que ${\displaystyle L}$ é livre de contexto deve ser falsa.

Enquanto o lema do bombeamento é muitas vezes uma ferramenta útil para provar que uma determinada linguagem não é livre de contexto, o mesmo não dá uma caracterização completa das linguagens livres de contexto. Se uma linguagem não satisfaz a condição dada pelo lema do bombeamento, temos estabelecido que ela não é livre de contexto. Por outro lado, há linguagens que não são livres de contexto, mas ainda satisfazem a condição dada pelo lema do bombeamento. Existem técnicas de provas mais poderosas disponíveis, tais como o lema de Ogden, mas estas técnicas também não dão uma caracterização completa das linguagens livres de contexto.

Ver também

• Lema do bombeamento para linguagens regulares
• Linguagens formais

Referências

• Bar-Hillel, Y.; Perles, M. and Shamir, E. (1961). «On formal properties of simple phrase-structure grammars». Zeitschrift fur Phonetik, Sprachwissenschaft, und Kommunikationsforschung. 14: 143–177  A referência emprega parâmetros obsoletos |coautor= (ajuda)
• Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X  Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.