# How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

Given the set of natural numbers, $$S = \{2^i|i\in\mathbb{N}\}$$ let $$L$$ be the language defined as the ternary representation of all numbers in $$S$$. How can you prove that this is not a regular language using the pumping lemma?

I cannot seem to find any sort of pattern for ternary representations of $$S$$, and so I'm finding it really difficult to prove this using the pumping lemma.

I tried to make a few strings in $$L$$ and got $$\{1, 11, 22, 121, 1012, 2101, \dots\}$$ but cannot find any sort of pattern that leads to using the pumping lemma. So, how would you prove that this is not a regular language using the pumping lmma? Thanks in advance.

## 1 Answer

This answer is a simpler version of Colin McQuillan's answer to the same question.

Suppose the language is regular. The pumping lemma gives strings $$u,v,w$$ such that every string $$x_n=u v^n w$$ is a power of $$2$$.

Interpreting these strings as numbers and writing $$d$$ and $$e$$ for the lengths of $$v$$ and $$w$$ respectively, we have $$x_n = u 3^{dn+e} + v 3^{d(n-1)+e} + v 3^{d(n-2)+e} + \dots + v 3^e + w.$$ So, $$x_{n+1}-3^dx_n = v3^e + w - 3^dw.$$

Note that the right-hand side is a constant as $$n$$ goes to infinity. Letting $$c$$ be the right-hand side, we have $$\frac{x_{n+1}}{x_n} - 3^d= \frac{c}{x_n}.$$

Since $$x_{n+1}$$ is a bigger power of 2 than $$x_n$$, $$\dfrac{x_{n+1}}{x_n}$$ is always an integer. That means the right-hand side is always an integer as well. Since $$\dfrac c{x_n}$$ goes to $$0$$ as $$n$$ goes to infinity, it must become 0 eventually.

Well, when it does become 0, we have $$\dfrac{x_{n+1}}{x_n}=3^d$$, which cannot happen since the left-hand side, a power of 2 that is greater than 1, can never be a power of 3.

Here is an easy exercise.

Exercise. Check that the above proof works the same if you replace 3 by any positive integer that is not a power of 2.