Lema de bombament per a llenguatges regulars

En la teoria de llenguatges formals, el lema del bombament per a llenguatges regulars descriu una propietat essencial de tot llenguatge regular. Informalment, diu que qualsevol paraula suficientment llarga en un llenguatge regular pot ser bombada - això és, repetir una secció en la meitat de la paraula un nombre arbitrari de vegades - per produir una nova paraula que també pertany al mateix llenguatge.

El lema de bombament fou enunciat per primera vegada per I. Bar-Hillel, M. Perles, I. Shamir en 1961.^[1] És útil per demostrar que un llenguatge específic no és regular.

Sigui ${\displaystyle L}$ un llenguatge regular. Aleshores existeix un enter ${\displaystyle p\geq 1}$ (al que anomenem "longitud de bombament" i que dependrà exclusivament de ${\displaystyle L}$) tal que qualsevol cadena ${\displaystyle w}$ pertanyent a ${\displaystyle L}$, de longitud major o igual que ${\displaystyle p}$, pot ser escrita com ${\displaystyle w=xyz}$ (p. ex. dividint ${\displaystyle w}$ en tres subcadenes), de forma que es satisfacin les següents condicions:

1. ${\displaystyle |y|\geq 1}$
2. ${\displaystyle |xy|\leq p}$
3. ${\displaystyle \forall i/\ i\geq 0,xy^{i}z\in L}$

${\displaystyle y}$ és la subcadena que pot ser bombada (esborrada o repetida un número ${\displaystyle i}$ de vegades com s'indica en (3), i la cadena resultant seguirà pertanyent a ${\displaystyle L}$). (1) significa que la cadena ${\displaystyle y}$ que es bomba ha de tenir com a mínim longitud u. (2) significa que ${\displaystyle y}$ ha d'estar dintre dels ${\displaystyle p}$ primers caràcters. No hi ha restriccions sobre de ${\displaystyle x}$ o ${\displaystyle z}$.

• J. LLopis, Aplicació del lema de bombament per demostrar que un llenguatge no és regular, (en castellà), ISSN:2659-8442.
• R. Béjar Hernández, P. Javier Álvarez, El lema de bombament per a llenguatges regulars (pdf), (en castellà), Universidad de Zaragoza.