Siguiente: Ejemplo: Un nivel arriba: Expresiones regulares Anterior: Minimización de autómatas

Lema de bombeo

Sea $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ un autómata finito con n estados. Una palabra $\sigma$ de longitud k define una sucesión de estados $S(\sigma)$ de longitud k+1 consistente de los estados por los que ``pasa'' la aplicación de la palabra $\sigma$ al autómata. Se tiene:

$$\begin{eqnarray*}\sigma=\mbox{\it nil\/}&\Rightarrow& S(\sigma)=[q_0] \\ \sigm... ...& S(\sigma)=S(\sigma_1)*[T_{\mbox{\scriptsize\it AF}}(\sigma)] \end{eqnarray*}$$

Si $k\geq n$ necesariamente al menos un estado ha de aparecer repetido en la sucesión $S(\sigma)$. Por tanto, se puede descomponer a $S(\sigma)$ en tres tramos, $S(\sigma)=S_1\cdot S_2\cdot S_3$, de manera tal que S₁ y S₂ son no-vacíos y sus extremos derechos coinciden. Esta descomposición de $S(\sigma)$ corresponde a una descomposición de $\sigma$ de la forma $\sigma=\sigma_1\sigma_2\sigma_3$ con $\mbox{\it long\/}(\sigma_2)>0$ y $T_{\mbox{\scriptsize\it AF}}(\sigma_1)=T_{\mbox{\scriptsize\it AF}}(\sigma_1\sigma_2)$. Así pues, la partícula no-vacía $\sigma_2$ está definiendo un bucle en el autómata. Por tanto, si $\sigma=\sigma_1\sigma_2\sigma_3$ fuese reconocida por el autómata, también ha de serlo cualquier palabra de la forma $\sigma_1\sigma_2^*\sigma_3$. 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 $n\geq 1$ tal que toda palabra $\sigma\in L$ con longitud al menos n admite una descomposición de la forma $\sigma=\sigma_1\sigma_2\sigma_3$ tal que

• $\mbox{\it long\/}(\sigma_2)>0$,
• $\mbox{\it long\/}(\sigma_1\sigma_3)\leq n$, y
• $\forall k\geq 0:\ \sigma_1\sigma_2^k\sigma_3\in L$.

En símbolos:

 

$$\forall L\in\{\mbox{\it Regulares\/}\}\exists n\geq 1\forall \sigma\in \mbox{\it Ent\/}^*:$$

$$% (\sigma\in L)\&(\mbox{\it long\/}(\sigma)\geq n)\ \Rightarrow\ ... ...n)\& \\ (\forall k\geq 0:\ \sigma_1\sigma_2^k\sigma_3\in L) \end{array}\right.$$ (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.

Siguiente: Ejemplo: Un nivel arriba: Expresiones regulares Anterior: Minimización de autómatas