Lema do bombeamento
Origem: Wikipédia, a enciclopédia livre.
Na teoria da linguagens formais na teoria da computabilidade, o lema do bombeamento (em inglês: pumping lemma ) diz que qualquer linguagem de dada classe pode ser "bombeada" ("pumped") e ainda pertencer àquela classe. A linguagem pode ser bombeada se qualquer string suficientemente longa na linguagem pode ser quebrada em pedaços (broken into pieces), algumas das quais podem ser repitidas arbitrariamente para produzir uma string mais longa na 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 bomeamento 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 linguagens de livre-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.
[editar] Referências
- Michael Sipser (1997). Introduction to the Theory of Computation. 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.
