Lema del bombeig per a llenguages regulars

En la teoria de llenguages formals, el lema del bombeig per a llenguages regulars descriu una propietat essencial de tot llenguage regular. Informalmente, diu que qualsevol paraula suficientment llarga en un llenguage regular pot ser bombejada - això és, repetir una secció en la mitat de la paraula un número arbitrari de voltes - per a produir una nova paraula que també pertany al mateix llenguage.

El lema de bombeig va ser enunciat per primera volta per Y. Bar-Hillel, M. Perles, E. Shamir en 1961. És útil per a demostrar que un llenguage específic no és regular.

Enunciat formal

Siga $L$ un llenguage regular. Llavors existix un sancer $p\ge 1$ (al que cridarem "llongitut de bombeig" i que dependrà exclusivament de $L$) tal que qualsevol cadena $w$ pertanyent a $L$, de llongitut major o igual que $p$, pot ser escrita com $w=xyz$ (p. eix. dividint $w$ en tres subcadena), de manera que se satisfan les següents condicions:

1. $|y|\ge 1$
2. $|xy|\le p$
3. $(\mathrm{\forall }n\ge 0)(x{y}^{n}z\in L)$

$y$ és la subcadena que pot ser bombejada (borrada o repetida un número $n$ de voltes com s'indica en (3), i la cadena resultant seguirà pertanyent a $L$). (1) significa que la cadena $y$ que es bombeja deu tindre com a mínim llongitut un. (2) significa que $y$ deu estar dins dels $p$ primers caràcters i que $x$ té una llongitut finita. No hi ha restriccions sobre $z$.

Us del lema

El lema del bombeig s'usa a sovint per a provar que un llenguage particular no és regular: una demostració per reducció a l'absurt (de que un llenguage no és regular) pot consistir en trobar una paraula (d'una llongitut requerida) en el llenguage, que carix de la propietat descrita en el lema del bombeig.

Per eixemple, del llenguage $L=\{a^n{b}^n:n\ge 0\}$ sobre l'alfabet $\Sigma =\{a,b\}$ pot demostrar-se que no és regular com seguix:

Supongam que $L$ és regular. La paraula

$w=a^p{b}^p$

a on $p$ és la constant del lema de bombeig, és una paraula de $L$.

Siga

$w=xyz$

una descomposició que complix les condicions del lema. Aplicant el lema, sabem que

$x{y}^{i}z\in L$

No obstant, com

$|xy|\le p,|y|>0$

necessàriament

$xy=a^k$

sent $k\le p$. Llavors,

$x=a^{k_1},y=a^{k_2}$

sent $k_1+k_2=k$ i $z=a^{p-k}{b}^p$.

El número de $a$ en la paraula $x{y}^{2}z\in L$, que pel lema pertany al llenguage $L$, és

$k_1+2k_2+p-k=k+k_2+p-k=k_2+p>p$

Per tant, la paraula té més $a$ que $b$, per lo que no pot ser una paraula de $L$.

La suposició de que $L$ és regular és incorrecta. Per tant, $L$ no és regular.