Lema de bombeo

Siendo $a^*b^*$ una expresión regular, podemos construir un autómata finito que acepta el lenguaje así definido, también podemos construir para cualquier $n\in\bbbn$ fijo un autómata finito adecuado ($a^nb^n$ sería una expresión regular extendida que define el lenguaje correspondiente que contiene una sola palabra).

Pero no podemos construir un autómata finito que acepte el lenguaje:

$$L_{ab}=\{a^nb^n\;\vert\;n\in\bbbn \} = \{\epsilon,ab,aabb,aaabbb,\dots\}$$

donde el parámetro $n$ no es fijo, sino se quiere que haya tantas $a$'s como $b$'s.

¿Por qué no podemos construir tal autómata?

• asumimos que tengamos un autómata finito $M$ con $k$ estados que acepta $L_{ab}$
• anotamos los estados de $M$ después de haber leído las palabras $a^i$ para $i=0,\dots,k$ (son $k+1$ palabras)
• pues serán (usando la ampliación de la función $\delta$):
  
  $$\delta^*(q_0,\epsilon), \delta^*(q_0,a), \delta^*(q_0,aa), \delta^*(q_0,aaa), \dots, \delta^*(q_0,a^k)$$
  
  

• Entonces, un estado tiene que aparecer por lo menos dos veces (se llama principio de los cajones (pigeonhole principle): si se quiere poner más calcetines que hay cajones en los cajones, por lo menos en un cajón acaban por lo menos dos calcetines)
• es decir: $\delta^*(q_0,a^i)=\delta^*(q_0,a^j)$ para algunos $i\not=j$
• Entonces:
  $$\begin{eqnarray*} \delta^*(q_0,a^ib^j) &=& \delta^*(\delta^*(q_0,a^i),b^j) ... ...elta^*(\delta^*(q_0,a^j),b^j) \\ &=& \delta^*(q_0,a^jb^j)\in F \end{eqnarray*}$$
  
  
  pues, el autómata también acepta $a^ib^j, i\not=j$ que no debe hacer. ¡Una contradicción!
• Entonces asumimos mal, es decir, no existe un autómata que acepte $L_{ab}$, o en otras palabras, $L_{ab}$ no es regular.

Observamos el comportamiento del siguiente autómata:

$$\begin{array}{lcccc} w_0 & = & 110 & & 10 \\ w_1 & = & 110 ... ...10 \\ & \dots & & & \\ w_k & = & x & y^k & z \\ \end{array}$$

Lema (de bombeo para lenguajes regulares): Sea $L$ un lenguaje regular (infinito). Entonces existe un $n\in\bbbn$ de tal manera que cada palabra $w\in L$ con $\vert w\vert\geq n$ se puede dividir en tres partes, $w=xyz$ cumpliéndose las tres propiedades:

1. $y\not=\epsilon$
2. $\vert xy\vert\leq n$
3. para todos los $k\geq 0: xy^kz\in L$

Comprobación (ideas principales):

• Sea $L$ un lenguaje regular (infinito).
• Entonces existe un autómata finito determinista $M$ que acepta $L$.
• Sea $n$ el número de estados de $M$ ($n=\vert Q\vert$).
• Sea $w$ una palabra con $\vert w\vert\geq n$ (tal palabra existe porque $L$ es infinito).
• Entonces se visita un estado de $M$ por lo menos dos veces.
• Escogemos el estado que se visita la primera vez dos veces, le llamamos $q$.
• La parte de $w$ que se lee hasta llegar la primera vez a $q$ llamamos $x$ (puede ser que $x=\epsilon$).
• La parte de $w$ que se lee hasta llegar la segunda vez a $q$ llamamos $y$ ( $y\not=\epsilon$ porque un bucle en un AFD tiene aristas con símbolos).
• La longitud $\vert xy\vert\leq n$ porque hemos recorrido un camino dondo solo un estado aparece dos veces.
• La parte que sobra para terminar aceptando $w$ llamamos $z$.
• Entonces dividimos $w$ en tres partes, es decir, $w=xyz$.
• $M$ acepta tanto $xz$, como $xyz$, como cualquier $xy^kz$ para todos los $k\geq 0$ porque podemos recorrer el bucle de $y$ tantas veces como queremos (esto se debe comprobar formalmente con inducción).

Entonces, comprobamos de nuevo que $L_{ab}$ no es regular, ahora usando el lema de bombeo:

• Asumimos que $L_{ab}$ sea regular.
• El lema de bombeo nos garantiza la existencia de un $n$ tal que se cumplen las propiedades para palabras $w$ con $\vert w\vert\geq n$.
• (Pensamos...): Elegimos $w=a^nb^n$. Obviamente $w\in L_{ab}$ y $\vert w\vert=2n\geq n$.
• El lema de bombeo nos garantiza la existencia de una partición $w=xyz$ con $y\not=\epsilon$, $\vert xy\vert\leq n$, y $\forall k\geq 0: xy^kz\in L_{ab}$. (No conocemos la partición en concreto, pero sus propiedades.)
• Porque $\vert xy\vert\leq n$ el prefijo $xy$ no contiene ninguna $b$.
• Porque $y\not=\epsilon$ la subpalabra $y$ contiene por lo menos una $a$.
• Todos las $b$s están en $z$.
• Tanto $xz=xy^0z\in L_{ab}$ como $xy^1z\in L_{ab}$ pero $xz$ contiene por lo menos una $a$ menos que $xyz$ (hemos quitado $y$).
• Eso es una contradicción porque $xz$ no debe estar dentro $L_{ab}$.
• Entonces $L_{ab}$ no puede ser regular.

Receta para el uso del lema de bombeo:

• Dado un lenguaje $L$.
• Queremos comprobar que $L$ no es regular.
• Comprobación con contradicción.
• Asumimos que $L$ sea regular.
• El lema de bombeo garantiza la existencia de un $n$ (pero no lo conocemos).
• Buscamos $w\in L$ (con un poco de sabiduría) que depende de $n$, tal que $\vert w\vert\geq n$
• El lema de bombeo garantiza la existencia de la partición de $w=xyz$ cumpliendo las 3 propiedades.
• Comprobamos (con un poco de sabiduría) que, independiente de la partición de $w$ en concreto (en los límites de las primeras dos propiedades), se produce una contradicción con la tercera propiedad.

Podemos describir dicha `receta' también como un juego para dos personas:

• Juego para un lenguaje $L$.
• Jugador 1 selecciona $n$.
• Jugador 2 selecciona $w\in L$ con $\vert w\vert\geq n$.
• Jugador 1 selecciona partición $w=xyz$ con $y\not=\epsilon$ y $\vert xy\vert\leq n$.
• Jugador 2 selecciona $k$.

• si $xy^kz\notin L$ gana jugador 2, sino gana jugador 1.
• si jugador 2 puede ganar siempre, entonces $L$ no es regular.

El lema de bombeo es el jugador 1, ¿quién es el jugador 2?

Otro Ejemplo:

$$L_{quad}=\{0^m\;\vert\;m \mbox{ es n\'umero cuadrado} \}$$

es decir, todas las cadenas de ceros que tienen un número cuadrado de símbolos.

• Asumimos que $L_{quad}$ sea regular.
• El lema de bombeo nos garantiza la existencia de un $n$ tal que se cumplen las propiedades para palabras $w$ con $\vert w\vert\geq n$.
• (Pensamos...): Elegimos $w=0^{n^2}$. Obviamente $w\in L_{quad}$ y $\vert w\vert=n^2\geq n$.
• El lema de bombeo nos garantiza la existencia de una partición $w=xyz$ con $y\not=\epsilon$, $\vert xy\vert\leq n$, y $\forall k\geq 0: xy^kz\in L_{quad}$. (No conocemos la partición en concreto, pero sus propiedades.)
• Tanto $xyz\in L_{quad}$ como $xy^2z\in L_{quad}$ con $y\not=\epsilon$.
• Tenemos entonces:
  $$\begin{eqnarray*} n^2 &=& \vert xyz\vert \quad\mbox{porque es $w$}\\ &<& \ver... ...mbi\'en $\vert y\vert\leq n$}\\ &<& n^2 +2n +1 \\ &=&(n+1)^2 \end{eqnarray*}$$
  
  

• Eso es una contradicción porque $xy^2z$ no puede ser una palabra cuya longitud es un número cuadrado entre dos números cuadrados consecutivos.
• Entonces $L_{quad}$ no puede ser regular.

Dos comentarios más:

• Este lema de bombeo solo garantiza una propiedad para lenguajes regulares, es decir, todos los lenguajes regulares (infinitos) la tienen, pero pueden existir más lenguajes que la tengan, o en otras palabras, pueden existir lenguajes $L$ donde encontramos tal $n$ y la división de $w$ en $xyz$ con todas las propiedades, pero $L$ no es regular.
• Con el lema de bombeo también se puede derivar: si tal $w\notin L$ entonces $xy^kz\notin L$ (el argumento es fácil: no hace falta que lleguemos a una estado final en la comprobación, lo importante eran los caminos recorridos).

Reglas de mano:

• Un lenguaje es regular si independientemente de la longitud de la palabra de entrada, hay que memorizar solamente una cantidad constante de información (en el caso de $L_{ab}$ deberíamos memorizar el número de $a$'s que no es constante).
• La comprobación formal se realiza con el lema de bombeo.
• El lema de bombeo se usa para comprobar que un lenguaje no es regular, para comprobar que es regular, por ejemplo, se construye un autómata finito, una expresión regular, o una grámatica de tipo 3.

Pero ojo, existen lenguajes regulares que tienen que ver con números:

$$L_{tres}=\{w\;\vert\;w \mbox{ es codificaci\'on de un n\'umero divisible por 3} \}$$

Ejercicio: contruye un autómata finito que acepte $L_{tres}$.