Sea $L:={1, 11, 1001,\dots}$ el idioma con el alfabeto ${0,1}$ que está formado por todas las potencias $3^n, n=0,1,\dots$ escrito en notación binaria. ¿Cómo probar que $L$ no es regular?
Respuestas
¿Demasiados anuncios?
El lema de bombeo es tu amigo pues dice que si $L$ eran regulares, de que habría una longitud de $n$ de manera tal que todos los $w\in L$ $|w|>n$ se puede dividir en $w=xyz$ $y\ne\epsilon$ tal que $xy^kz\in L$ todos los $k\in\mathbb N_0$. No sabemos $n$, sino que la consideran uno de esos palabra $w$ y deje $a,b,c$ ser los números representados por las cadenas binarias $x,y,z$ y deje $N_k$ ser el número rpresented por $xy^kz$. A continuación, $$N_{k+1}=(N_k-c)\cdot 2^{|y|}+b\cdot 2^{|z|}+c$$ y como $N_k\to\infty$ (debido a $x$ comienza con un $1$), tenemos $\frac{N_{k+1}}{N_k}\to 2^{|y|}$$k\to\infty$. Por otro lado, $\frac{N_{k+1}}{N_k}$ es siempre una potencia de $3$. Por lo tanto para suficientemente grande $k$, nos encontramos con $m$$|3^m-2^{|y|}|<\frac12$, es decir,$3^m=2^{|y|}$. Esto sólo es posible si $m=|y|=0$, contradiciendo $|y|\ne 0$.
user1525612
Puntos
118
Utilizar el lema de bombeo:
Asumir en la contradicción de que $L$ es regular, por lo que cualquier palabra $w$ $L$ más de $n$, puede ser dividido en $w=xyz$ tal forma que:
$y$ no es palabra vacía
$|xy| \le n$
y para cada una de las $k$, la palabra $xy^kz$$L$.
Ahora, vamos a $n=3$, e $w=1001$ tal que $x = \emptyset, y=100$$z=1$. Tome $k = 2$, tendremos una nueva palabra $w' = 1001001$, que es en binario $73$, que NO es en $L$.
Es la segunda vez que me dan una respuesta, voy a estar contento de tener una retroalimentación de los demás.
