4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.