Siguiente: Ejemplo: Un nivel arriba: Lema de bombeo Anterior: Lema de bombeo

Ejemplo:

El lenguaje de palabras equilibradas

$$L=\{0^n1^n\vert n\geq 0\}$$

no es regular. En efecto, si lo fuera, existiría n₀>0 que satisficiera 4.37 (con n₀ en lugar de n). Sea $n>\left\lceil\frac{n_0}{2}\right\rceil$. Entonces habrían de existir $\sigma_1,\sigma_2,\sigma_3$ tales que $0^n1^n=\sigma_1\sigma_2\sigma_3$ y, para cualquier $k\geq 0$, $\sigma_1\sigma_2^k\sigma_3\in L$. Un minuto de reflexión basta para ver que esto no es posible.