Prove that $\{1, 11, 1001,\dots\}$ is an irregular language

Question

Let $L:=\{1, 11, 1001,\dots\}$ be the language with alphabet $\{0,1\}$ which is formed by all powers $3^n, n=0,1,\dots$ written in binary notation. How to prove that $L$ is not regular?

Answer 1

The pumping lemma is your friend as it states that if $L$ were regular, there'd be a length $n$ such that all $w\in L$ with $|w|>n$ can be split into $w=xyz$ with $y\ne\epsilon$ such that $xy^kz\in L$ for all $k\in\mathbb N_0$. We do not know $n$, but consider one such word $w$ and let $a,b,c$ be the numbers represented by the binary strings $x,y,z$ and let $N_k$ be the number rpresented by $xy^kz$. Then $$N_{k+1}=(N_k-c)\cdot 2^{|y|}+b\cdot 2^{|z|}+c$$ and as $N_k\to\infty$ (because $x$ begins with a $1$), we have $\frac{N_{k+1}}{N_k}\to 2^{|y|}$ as $k\to\infty$. On the other hand, $\frac{N_{k+1}}{N_k}$ is always a power of $3$. Thus for sufficiently big $k$, we find $m$ with $|3^m-2^{|y|}|<\frac12$, i.e. $3^m=2^{|y|}$. This is only possible if $m=|y|=0$, contradicting $|y|\ne 0$.

Answer 2

Use the pumping lemma:

Assume in contradiction that $L$ is regular, so any word $w$ in $L$ longer than $n$, can be divided into $w=xyz$ such that:

1. $y$ is not empty word

2. $|xy| \le n$

3. and for each $k$, the word $xy^kz$ is in $L$ too.

Now, let $n=3$, and $w=1001$ such that $x = \emptyset, y=100$ and $z=1$. Take $k = 2$, we'll get a new word $w' = 1001001$, which is in binary $73$, which is NOT in $L$.

It's the second time I give an answer, I'll be glad to have a feedback from the others.