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

Ejemplo:

Sea L el lenguaje consistente de las representaciones en binario, sin ceros a la izquierda, de los números primos. L no puede ser regular. En efecto, supongamos que para todo $\sigma=e_0\cdots e_{k-1}\in(0+1)^*$

\begin{displaymath}1\sigma\in L\ \Leftrightarrow\ 2^k+\sum_{j=0}^{k-1}e_j 2^{k-1-j}\mbox{\rm es primo,}\end{displaymath}

y, por un momento, supongamos que L es regular. El teorema de Euclides sobre la infinidad de los números primos muestra que en L hay cadenas arbitrariamente largas. Elijamos n>0 que satisfaga 4.37, y consideremos un primo p>2n, es decir, un primo cuya representación en binario tenga longitud superior a n. Entonces podemos encontrar $\sigma_1,\sigma_2,\sigma_3$ tales que para todo $j\geq 0$, $\left(\sigma_1\sigma_2^j\sigma_3\right)_2$ es un número primo. Sea $n_i=\left(\sigma_i\right)_2$, i=1,2,3, el número representado en binario por la partícula $\sigma_{i}$ y sea ki la longitud de $\sigma_{i}$. Para j=p, el número $q=\left(\sigma_1\sigma_2^p\sigma_3\right)_2$ ha de ser primo. Se tiene, al agrupar a la representación en binario de q en un primer bloque a la derecha de k1 bits, p bloques contiguos de k2 bits hacia la izquierda y uno último de k3 bits, que
 
q = $\displaystyle \left[n_1 2^{pk_2+k_3}\right] +\left[\left[n_2 2^{(p-1)k_2+k_3}\r...
...\left[n_2 2^{k_2+k_3}\right] +\left[n_2 2^{k_3}\right]\right] +\left[n_3\right]$  
  = $\displaystyle n_1 2^{pk_2+k_3} +n_2 2^{k_3}\left[2^{(p-1)k_2}+\cdots+ 2^{k_2} + 1\right] +n_3$ (49)
  = $\displaystyle n_1 2^{pk_2+k_3} +n_2 2^{k_3}\left[\frac{2^{pk_2}- 1}{2^{k_2}- 1}\right] +n_3$  

Ahora, por el Teorema Pequeño de Fermat, $2^{p-1}\equiv1\mbox{\rm mod }p$. Por tanto, $2^{(p-1)k_2}\equiv1\mbox{\rm mod }p$, y $2^{pk_2}\equiv2^{k_2}\mbox{\rm mod }p$, pues 2pk2=2k22(p-1)k2. Sea $s=\left[2^{(p-1)k_2}+\cdots+ 2^{k_2} + 1\right]$. Entonces (2k2- 1)s=2pk2- 1. Por tanto, $(2^{k_2}- 1)s\equiv(2^{k_2}-1)\mbox{\rm mod }p$. Así, módulo p, se tiene las igualdades

\begin{displaymath}0\equiv(2^{k_2}- 1)s -(2^{k_2}- 1)=(2^{k_2}- 1)(s-1).\end{displaymath}

Por consiguiente p debe dividir a (2k2- 1) o a (s-1). No puede dividir a (2k2- 1) pues $2^{k_2}\leq 2^n<p$ ya que $1\leq k_2\leq n$. Por tanto p debe dividir a s-1. Se sigue que $s\equiv 1\mbox{\rm mod }p$. Al tomar congruencias módulo p en 4.38 se tiene

\begin{eqnarray*}q &\equiv& \left[n_1 2^{pk_2+k_3} +n_2 2^{k_3}+n_3\right]\mbox{...
...\
&\equiv& p\mbox{\rm mod }p \\
&\equiv& 0\mbox{\rm mod }p
\end{eqnarray*}


es decir, el primo q debe ser divisible por el primo p. Esto es una contradicción y por tanto L no puede ser regular.
next up previous contents
Siguiente: Propiedades de lenguajes regulares Un nivel arriba: Lema de bombeo Anterior: Ejemplo:
Guillermo Morales-Luna
2000-06-27