Skip to main content
Minor improvement.
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

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$$$$ 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$$ Let$$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 constant on the right-hand side, i.e., $c=v3^e + w - 3^dw$, we have $$\frac{x_{n+1}}{x_n} = 3^d + \frac{c}{x_n} = 3^d +o(1)\ \text{ as }n\to\infty$$$$\frac{x_{n+1}}{x_n} - 3^d= \frac{c}{x_n}.$$

Since the left-hand side, as$x_{n+1}$ is a quotient of two powersbigger power of 2 than $x_n$, must$\dfrac{x_{n+1}}{x_n}$ is always be an integer,. That means the right-hand side is always an integer as well. Since the right-hand side$\dfrac c{x_n}$ goes to $3^d$$0$ as $n$ goes to infinity, it must be $3^d$become 0 eventually. Or we can say, once the term $o(1)$ is smaller than 1

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


ExerciseHere is an easy exercise. (A minute or two)

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

This answer is 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$$ Let the $c$ be the constant on the right-hand side, i.e., $c=v3^e + w - 3^dw$, we have $$\frac{x_{n+1}}{x_n} = 3^d + \frac{c}{x_n} = 3^d +o(1)\ \text{ as }n\to\infty$$

Since the left-hand side, as a quotient of two powers of 2, must always be an integer, the right-hand side is always an integer as well. Since the right-hand side goes to $3^d$, it must be $3^d$ eventually. Or we can say, once the term $o(1)$ is smaller than 1, it must be 0. However, the left-hand side, as a power of 2 that is greater than 1, can never be a power of 3. This is a contradiction.


Exercise. (A minute or two) Check that the above proof works the same if you replace 3 by any positive integer that is not a power of 2.

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.

Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

This answer is 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$$ Let the $c$ be the constant on the right-hand side, i.e., $c=v3^e + w - 3^dw$, we have $$\frac{x_{n+1}}{x_n} = 3^d + \frac{c}{x_n} = 3^d +o(1)\ \text{ as }n\to\infty$$

Since the left-hand side, as a quotient of two powers of 2, must always be an integer, the right-hand side is always an integer as well. Since the right-hand side goes to $3^d$, it must be $3^d$ eventually. Or we can say, once the term $o(1)$ is smaller than 1, it must be 0. However, the left-hand side, as a power of 2 that is greater than 1, can never be a power of 3. This is a contradiction.


Exercise. (A minute or two) Check that the above proof works the same if you replace 3 by any positive integer that is not a power of 2.