O que é o lema do bombeamento?

O lema do bombeamento para linguagens regulares descreve uma propriedade essencial de todas as linguagens regulares: todas as cadeias suficientemente longas duma dada linguagem regular podem ser "bombeadas", isto é, cada uma dessas cadeias tem uma subcadeia central que pode ser repetida arbitrariamente a fim de produzir uma nova cadeia que também pertence à mesma linguagem.

O lema do bombeamento foi primeiro enunciado por Y. Bar-Hillel, Micha Perles e Eli Shamir em 1961.^[1] Ele é útil para provar que uma linguagem não é regular. Há vários outros lemas do bombeamento, todos com objetivos similares