Lenguajes regulares y lema de bombeo

Un lenguaje regular se reconoce con un autómata finito. Las expresiones regulares matemáticas se construyen a partir de símbolos, ∅ y ε mediante unión, concatenación y estrella de Kleene.

La estrella repite cero o más veces. En 0*1*, las cantidades de ceros y unos son independientes; en {0ⁿ1ⁿ:n≥0} se exige que sean iguales. Esa relación adicional cambia el problema.

Si L es regular, existe p≥1 tal que para toda palabra w∈L con |w|≥p existe un corte w=xyz con |xy|≤p, |y|>0 y xyⁱz∈L para todo entero i≥0.

p sirve para todas las palabras largas, pero el corte puede depender de w. El bloque y es no vacío y queda completo entre los primeros p símbolos. x y z sí pueden ser vacíos.

Un DFA con p estados que lee al menos p símbolos hace p+1 visitas contando la inicial. Por el principio del palomar, dos visitas de esos primeros pasos coinciden.

Llamamos x al prefijo anterior a la primera visita, y al bloque entre ambas y z al resto. Como las posiciones son distintas, y no es vacío; como la segunda visita ocurre antes o al consumir el símbolo p, |xy|≤p.

Si leer y desde un estado devuelve al mismo estado, repetirlo i veces también. Para i=0 se omite y; para i=1 queda la palabra original.

Después se procesa el mismo sufijo z desde el mismo estado, de modo que se llega al mismo aceptante. No se exige que y sea una sola letra ni que sus letras sean iguales.

Suponemos regularidad y recibimos un p desconocido. Elegimos w en función de p. El lema podría ofrecer cualquier corte válido; hay que demostrar que todos fracasan para alguna repetición.

La negación sigue este orden: para todo p, existe w suficientemente larga tal que para todo corte válido existe i≥0 con xyⁱz fuera del lenguaje. i puede depender del corte. Una división mala por sí sola no contradice que exista otra buena.

Sus primeros p símbolos son todos ceros, así que todo corte con |xy|≤p tiene y=0ᵏ para algún 1≤k≤p.

Las cantidades son diferentes para cualquier k permitido, incluida k=p. Así todos los cortes válidos contradicen el lema.

Si L es finito, elegimos p mayor que todas sus longitudes. No hay ninguna w∈L con |w|≥p, así que la condición se cumple vacíamente.

Si un regular sí contiene una palabra suficientemente larga, el bloque y no vacío produce palabras de longitudes cada vez mayores. Así los ciclos permiten reconocer infinitas palabras con finitos estados.

Negar el lema demuestra no regularidad. Cumplirlo en unos ejemplos o no encontrar contradicción no demuestra regularidad. Para probar regularidad construimos un autómata, una expresión regular o una combinación por cierres.

Incluso la propiedad completa de bombeo puede cumplirse en un lenguaje no regular. El siguiente contraste separa la propiedad lógica de una intuición basada en unos pocos cortes.

Los regulares son cerrados por intersección y complemento. Si intersectar un lenguaje con un regular produce uno que sabemos no regular, el primero tampoco puede ser regular.

También podemos distinguir prefijos por sufijos. Si infinitos prefijos requieren respuestas diferentes ante alguna continuación, un DFA necesitaría infinitos estados. Esta es la idea del criterio de Myhill–Nerode.