Sea
un autómata finito con n estados. Una palabra
de longitud k define una sucesión de estados
de longitud k+1 consistente de los estados por los que ``pasa'' la aplicación de la palabra
al autómata. Se tiene:
Si
necesariamente al menos un estado ha de aparecer repetido en la sucesión .
Por tanto, se puede descomponer a
en tres tramos,
,
de manera tal que S1 y S2 son no-vacíos y sus extremos derechos coinciden. Esta descomposición de
corresponde a una descomposición de
de la forma
con
y
.
Así pues, la partícula no-vacía
está definiendo un bucle en el autómata. Por tanto, si
fuese reconocida por el autómata, también ha de serlo cualquier palabra de la forma
.
Puesto de manera muy esquemática, se tiene que toda palabra reconocida por un autómata finito cuya longitud exceda al número de estados en el autómata necesariamente ha de contener una partícula no-vacía que se ``bombea''.
Lema 7.1 (de Bombeo)
Si L es un lenguaje regular entonces existe un entero
tal que toda palabra
con longitud al menos n admite una descomposición de la forma
tal que
,
,
y
.
En símbolos:
(48)
En efecto, si L es regular y es reconocido por un autómata finito AF, entonces el n cuya existencia se asevera en el lema es, precisamente, el número de estados en AF.
La proposición 4.37 es una condición necesaria para los lenguajes regulares. Consecuentemente, cualquier lenguaje que no la satisficiere no puede ser regular.