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 ⁿxy ⁿ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, ${\displaystyle 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 ${\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. 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 ${\displaystyle s=a^{p}b^{p}c^{p}}$ em ${\displaystyle L}$. O lema do bombeamento nos diz que pode ser escrito na forma ${\displaystyle s=uvxyz}$, onde ${\displaystyle u,v,x,y}$, and ${\displaystyle z}$ são subcadeias, de tal forma que ${\displaystyle |vxy|\leq p}$, ${\displaystyle |vy|\geq 1}$, e${\displaystyle uv^{i}xy^{i}z}$ pertence a ${\displaystyle L}$ para cada inteiro ${\displaystyle i\geq 0}$. Escolhendo s e o fato de ${\displaystyle |vxy|\leq p}$, vê-se facilmente que a substring ${\displaystyle vxy}$ não pode conter mais do que duas letras distintas. Ou seja, temos uma das cinco possibilidades para ${\displaystyle vxy}$:

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

Para cada caso, é facilmente verificado que ${\displaystyle uv^{i}xy^{i}z}$ não contem iguais números para cada letra em cada ${\displaystyle i\neq 1}$. Então, ${\displaystyle uv^{2}xy^{2}z}$ não tem a forma ${\displaystyle a^{i}b^{i}c^{i}}$. Isso contradiz a definição de ${\displaystyle L}$. Portanto, o que assumimos no início para ${\displaystyle 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

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.