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. És útil per demostrar que un llenguatge específic no és regular.

Enunciat formal

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

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

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

Enllaços externs

• 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.