Lema do bombeamento para linguagens de livre-contexto

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

Definição Formal

Se uma linguagem L é de livre-contexto, então existe um número inteiro p ≥ 1 onde, se s é uma cadeia qualquer em L com |s| ≥ p (onde p é o comprimento do bombeamento), então ela pode ser dividida em cinco partes

s = uvxyz

em que u, v, x, y e z são as subcadeias, e as condições |vxy| ≤ p, |vy| ≥ 1, e

uv^nxy^nz pertencem a L para cada inteiro n ≥ 0, devem ser obedecidas.

Definição Informal e Explicação

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

Essa propriedade é uma propriedade de todas as cadeias da linguagem de tamanho pelo menos p, onde p é uma constante chamada de comprimento do bombeamento -- isso varia entre as linguagens de livre-contexto.

Considere s uma cadeia de tamanho pelo menos p que pertence à linguagem.

O lema do bombeamento afirma que s pode ser dividida em cinco subcadeias, ${\displaystyle s=uvxyz}$, onde vy é não-vazia e o tamanho de vxy é no máximo p, de tal forma que repetindo v e y qualquer (e igualmente) número de vezes em s produz uma cadeia que ainda pertence à linguagem (é possível e frequentemente útil repetir as cadeias zero vezes, removendo v e y da cadeia). Esse processo de "bombear" cópias adicionais de v e y é o que dá o nome do lema do bombeamento.

Note que linguagens finitas (que são regulares e portanto de livre-contexto) obedecem ao lema do bombeamento trivialmente tendo p igual ao maximo tamanho da cadeia em L mais un. Como não há cadeias desse tamanho, o lema do bombeamento não é violado.

O lema do bombemento é frequentemente usado para provar que uma dada linguagem não é de livre-contexto mostrando que para cada p, nós podemos achar uma cadeia s de tamanho pelo menos p na linguagem que não possui as propriedades mostradas acima, isto é, ela não pode ser "bombeada" sem produzir cadeias que não estão na linguagem.

Uso do lema

O lema do bombeamento para linguagens de livre-contexto pode ser usado para mostrar que certa linguagem não é de livre-contexto.

Por exemplo, nós podemos mostrar que a linguagem ${\displaystyle L=\lbrace a^{i}b^{i}c^{i}|i>0\rbrace }$ não é de livre-contexto usando o lema do bombemento numa prova por contradição. Primeiramente, assumimos que ${\displaystyle L}$ é de livre-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, de tal forma que ${\displaystyle |vxy|\leq p}$, ${\displaystyle |vy|\geq 1}$, e ${\displaystyle uv^{i}xy^{i}z}$ pertence à ${\displaystyle L}$ para todo inteiro ${\displaystyle i\geq 0}$. Por nossa escolha de ${\displaystyle s}$ e pelo fato de ${\displaystyle |vxy|\leq p}$, é facilmente visto que a subcadeia ${\displaystyle vxy}$ não pode conter mais que duas letras diferentes. Então, temos 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}$ sendo ${\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}$ sendo ${\displaystyle j+k\leq p}$.
5. ${\displaystyle vxy=c^{j}}$ para algum ${\displaystyle j\leq p}$.

Para cada caso, é facilmente verificado que ${\displaystyle uv^{i}xy^{i}z}$ não contém números iguais de cada letra para qualquer ${\displaystyle i\neq 1}$. Assim, ${\displaystyle uv^{2}xy^{2}z}$ não tem a forma de ${\displaystyle a^{i}b^{i}c^{i}}$. Isso contradiz a definição de ${\displaystyle L}$. Portanto, nossa suposição inicial que ${\displaystyle L}$ é de livre-contexto é falsa.

Enquanto que o lema do bombeamento é geralmente uma ferramenta útil para provar que dada linguagem não é de livre-contexto, ela não dá uma completa caracterização de uma linguagem de livre-contexto. Se uma linguagem não satisfaz a condição dada pelo lema do bombeamento, nós estabelecemos que ela não é de livre-contexto. Porém, há linguagens que não são de livre-contexto, mas satisfazem a condição dada pelo lema do bombeamento. Existem técnicas de prova mais poderosas disponíveis, como o lema de Ogden, mas essas técnicas também não dão uma caracterização completa das linguagens de livre-contexto.

Ver também

• Lema do bombeamento para linguagens regulares
• Linguagem formal

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 (2007). Introdução à Teoria da Computação. [S.l.]: Thomson Learning. ISBN 978-85-221-0499-4  Seção 1.4: Linguagens Não-Regulares, pp. 79–85. Seção 2.3: Linguagens Não-livres-de-contexto, pp. 128–133.