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)^*$

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

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>2ⁿ, 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 k_i 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 k₁ bits, p bloques contiguos de k₂ bits hacia la izquierda y uno último de k₃ bits, que

 

$$\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]$$ q =

$$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)

$$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 2^pk₂=2^k₂2^(p-1)k₂. Sea $s=\left[2^{(p-1)k_2}+\cdots+ 2^{k_2} + 1\right]$. Entonces (2^k₂- 1)s=2^pk₂- 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

$$0\equiv(2^{k_2}- 1)s -(2^{k_2}- 1)=(2^{k_2}- 1)(s-1).$$

Por consiguiente p debe dividir a (2^k₂- 1) o a (s-1). No puede dividir a (2^k₂- 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.
Siguiente: Propiedades de lenguajes regulares Un nivel arriba: Lema de bombeo Anterior: Ejemplo: