next up previous contents
Siguiente: Ejemplo: Un nivel arriba: Lema de bombeo Anterior: Lema de bombeo

Ejemplo:

El lenguaje de palabras equilibradas

\begin{displaymath}L=\{0^n1^n\vert n\geq 0\}\end{displaymath}

no es regular. En efecto, si lo fuera, existiría n0>0 que satisficiera 4.37 (con n0 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.

Guillermo Morales-Luna
2000-06-27