Lema del bombeo para lenguajes regulares

En la teoría de lenguajes formales, el lema del bombeo para lenguajes regulares describe una propiedad esencial de todo lenguaje regular. Informalmente, dice que cualquier palabra suficientemente larga en un lenguaje regular puede ser bombeada - eso es, repetir una sección en la mitad de la palabra un número arbitrario de veces - para producir una nueva palabra que también pertenece al mismo lenguaje.

El lema de bombeo fue enunciado por primera vez por Y. Bar-Hillel, M. Perles, E. Shamir en 1961.^[1]​ Es útil para demostrar que un lenguaje específico no es regular.

Enunciado formal

Sea ${\displaystyle L}$  un lenguaje regular. Entonces existe un entero ${\displaystyle p\geq 1}$  (al que llamaremos "longitud de bombeo" y que dependerá exclusivamente de ${\displaystyle L}$ ) tal que cualquier cadena ${\displaystyle w}$  perteneciente a ${\displaystyle L}$ , de longitud mayor o igual que ${\displaystyle p}$ , puede ser escrita pop como ${\displaystyle w=xyz}$  (p. ej. dividiendo ${\displaystyle w}$  en tres subcadenas), de forma que se satisfacen las siguientes condiciones:

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

${\displaystyle y}$  es la subcadena que puede ser bombeada (borrada o repetida un número ${\displaystyle i}$  de veces como se indica en (3), y la cadena resultante seguirá perteneciendo a ${\displaystyle L}$ ). (1) significa que la cadena ${\displaystyle y}$  que se bombea debe tener como mínimo longitud uno. (2) significa que ${\displaystyle y}$  debe estar dentro de los ${\displaystyle p}$  primeros caracteres. No hay restricciones acerca de ${\displaystyle x}$  o ${\displaystyle z}$ .

Uso del lema

El lema del bombeo se usa a menudo para probar que un lenguaje particular no es regular: una demostración por reducción al absurdo (de que un lenguaje no es regular) puede consistir en encontrar una palabra (de una longitud requerida) en el lenguaje, que carece de la propiedad descrita en el lema del bombeo.

Por ejemplo, del lenguaje ${\displaystyle L=\{a^{n}b^{n}\ :n\geq 0\}}$  sobre el alfabeto ${\displaystyle \Sigma =\{a,b\}}$  puede demostrarse que no es regular como sigue:

Supongamos que ${\displaystyle L}$  es regular. La palabra

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

donde ${\displaystyle p}$  es la constante del lema de bombeo, es una palabra de ${\displaystyle L}$ .

Sea

${\displaystyle w=xyz}$ 

una descomposición que cumple las condiciones del lema. Aplicando el lema, sabemos que

${\displaystyle xy^{i}z\in L}$ 

Sin embargo, como

${\displaystyle |xy|\leq p,\ |y|>0}$ 

necesariamente

${\displaystyle xy=a^{k}}$ 

siendo ${\displaystyle k\leq p}$ . Entonces,

${\displaystyle x=a^{k_{1}},\ y=a^{k_{2}}}$ 

siendo ${\displaystyle k_{1}+k_{2}=k}$  y ${\displaystyle z=a^{p-k}b^{p}}$ .

El número de ${\displaystyle a}$  en la palabra ${\displaystyle xy^{2}z\in L}$ , que por el lema pertenece al lenguaje ${\displaystyle L}$ , es

${\displaystyle k_{1}+2k_{2}+p-k=k+k_{2}+p-k=k_{2}+p>p}$ 

Por tanto, la palabra tiene más ${\displaystyle a}$  que ${\displaystyle b}$ , por lo que no puede ser una palabra de ${\displaystyle L}$ .

La suposición de que ${\displaystyle L}$  es regular es incorrecta. Por tanto, ${\displaystyle L}$  no es regular.

Referencias

1. Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.

Enlaces externos

• Ejemplos: aplicación del lema de bombeo para demostrar que un lenguaje no es regular

•   Datos: Q2292874