Lema do bombeamento
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2021) |
Na teoria da linguagens formais na teoria da computabilidade, o lema do bombeamento ou lema da bombagem (em inglês: pumping lemma) diz que qualquer linguagem infinita de dada classe pode ser "bombeada" (pumped) e ainda pertencer àquela classe (as linguagens finitas são todas regulares). A linguagem pode ser bombeada se qualquer cadeia suficientemente longa na linguagem pode ser quebrada em pedaços, alguns dos quais podem ser repetidos um número arbitrário de vezes para produzir uma cadeia mais longa na linguagem. Por outras palavras, o acto de repetir a dita subcadeia, não faz com que a palavra "resultante" dessa repetição saia da linguagem. As provas desses lemas tipicamente requerem combinatória tal qual o princípio da casa dos pombos.
Os dois exemplos mais importantes são lema do bombeamento para linguagens regulares (em inglês: pumping lemma for regular languages) e o lema do bombeamento para linguagens de livre-contexto (em inglês: pumping lemma for context-free languages). Lema de Ogden é o segundo maior lema do bombeamento para linguagem livre de contexto.
Estes lema podem ser usados para determinar se uma linguagem qualquer não é dada classe de linguagem. No entanto, elas não podem ser usadas para determinar se uma linguagem está em dada classe, já que satisfazer o lema do bombeamento é uma condição necessária, mas não suficiente, para se fazer parte da classe.
Referências[editar | editar código-fonte]
- Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-XSection 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.