Lema do bombeamento para linguagens livre de contexto
# Lema do bombeamento para linguagens livre de contexto

O lema do bombeamento para linguagens livres de contexto, também conhecido como o lema Bar-Hillel, é um lema que que sua propriedade é compartilhada por todas as linguagens livres de contexto. Declaração Formal Se uma linguagem L é livre de contexto, então existe algum inteiro p ≥ 1 tal que qualquer cadeia s em L com | s | ≥ p (onde p é um "comprimento de bombeamento") pode ser escrita como

## Declaração formal

Se uma linguagem L é livre de contexto, então existe algum inteiro p ≥ 1 tal que qualquer cadeia s em L com | s | ≥ p (onde p é um "comprimento de bombeamento") pode ser escrita como
    s = uvxyz
com as subcadeias u, v, x, y e z, de tal modo que
    1. |vxy| ≤ p,
    2. |vy| ≥ 1, e
    3. uv$^n$xy$^n$z pertence a L para todo n ≥ 0.

## Declaração Informal e explicação

O lema do bombeamento para linguagens livres de contexto (chamado apenas "o lema do bombeamento" para o resto deste artigo) descreve uma propriedade que todas as linguagens livres de contexto possuem. Propriedade que todas as cadeias da linguagem que têm comprimento de pelo menos p, onde p é uma constante chamada de bombeamento de comprimento que varia entre as linguagens livres de contexto. E s é uma sequência de tamanho pelo menos p, que está na linguagem.
Os estados de bombeamento de s podem ser dividida em cinco subcadeias, $s=uvxyz$ onde vy não pode ser vazia e o comprimento de vxy é no máximo de p, de tal modo que qualquer repetição de v e y produz uma cadeia s que ainda está na linguagem. Este processo de "bombear" cópias adicionais de v e y é o que dá o lema do bombeamento seu nome. Observe que as linguagens finitas (que são regulares e, portanto, livre de contexto) obedecem ao lema do bombeamento trivialmente por ter p igual ao comprimento máximo da 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 cada p, podemos encontrar alguma cadeia s de comprimento pelo menos p na linguagem que não tem as propriedades descritas acima, ou seja, que ele não pode ser "bombeada", sem conseguir produzir alguma cadeia da linguagem.

## Uso do lema

Por exemplo, podemos mostrar que a linguagem $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. Em primeiro lugar, assumimos que L é livre de contexto. Pelo lema de bombagem, existe um número inteiro p que é o comprimento de bombeamento da linguagem. Considere a cadeia $s=a^{p}b^{p}c^{p}$ em $L$. O lema do bombeamento nos diz que pode ser escrito na forma $s=uvxyz$, onde $u,v,x,y$, and $z$ são subcadeias, de tal forma que $|vxy|\leq p$, $|vy|\geq 1$, e$uv^{i}xy^{i}z$ pertence a $L$ para cada inteiro $i\geq 0$. Escolhendo s e o fato de $|vxy|\leq p$, vê-se facilmente que a substring $vxy$ não pode conter mais do que duas letras distintas. Ou seja, temos uma das cinco possibilidades para $vxy$:
* $vxy=a^{j}$ para cada $j\leq p$.
* $vxy=a^{j}b^{k}$ para cada $j$ e $k$ com $j+k\leq p$.
* $vxy=b^{j}$ para cada $j\leq p$.
* $vxy=b^{j}c^{k}$ para cada $j$ e $k$ com $j+k\leq p$.
* $vxy=c^{j}$ para cada $j\leq p$.
Para cada caso, é facilmente verificado que $uv^{i}xy^{i}z$ não contem iguais números para cada letra em cada $i\neq 1$. Então, $uv^{2}xy^{2}z$ não tem a forma $a^{i}b^{i}c^{i}$. Isso contradiz a definição de $L$. Portanto, o que assumimos no início para $L$, sendo livre de contexto é falso.
Enquanto o lema do bombeamento é muitas vezes uma ferramenta útil para provar que uma determinada linguagem não é livre de contexto, não dos da uma caracterização completa das linguagens livres de contexto. Se uma linguagem não satisfaz a condição dada pelo lema do bombeamento, sabemos que ela não é livre de contexto. Por outro lado, existem linguagens que não são livres de contexto, mas ainda satisfazem a condição dada pelo lema do bombeamento. Existem técnicas de prova mais poderosos disponíveis, tais como lema de Ogden, mas também não dão uma caracterização completa das linguagens livres de contexto.

## Veja também

* Lema do bombeamento para linguagens regulares
* Linguagens formais