It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it.But the powers of 2 represented in ternary appears to be non regular. Pumping lemma or residue classes is hard to apply as there seems to be very little pattern among the strings. How do I solve it?In general, for what powers of $k$ represented in base $r$, is the set regular?
Proving the set of powers of 2 over ternary alphabet to be non regular.
automata theory;fl.formal languages
Here's an alternative solution (with detailed explanation) using Myhill-Nerode Theorem. I'll use base $3$ and $2$ for readibility, but the proof generalizes for arbitrary bases $r,k$ that are not powers of the same integer.(1) Show that given any ternary string $x$, there exists another string $y$ such that $xy$ is a power of $2$.Proof: Given any $x$ (letting $n$ be the number it represents), $\forall k$ and $c\in \{0,\ldots,3^k-1 \}$, there exists $y$ such that $xy$ represents $3^kn + c$. In fact, this characterizes all the numbers $xy$ can represent. Hence, finding the minimal $y$ such that $xy$ is a power of $2$ is depends on finding the smallest integer $k$ such that we have some power of $2$ in the interval $[3^kn,3^k(n+1)-1]$. Taking log base $2$, we need to find $k$ such that we have an integer in the interval $[k\log 3 + \log x, k\log3 + \log(x+1)]$ (dropping the $-1$ here is iffy, but simplifies calculations which do not rely on it). Notice that changing $k$ only affects the $k\log 3$ portion, so we can find a $k$ that gets us arbitrarily close to some integer.(2) Given some $x$ and the corresponding minimal $y$, show that there exists a string x' such that the corresponding minimal $y'$ has to be larger than $y$. Repeating this gives us infinitely many equivalence classes of strings.Proof Outline: Since $\log 2^m x = m + \log x$, given an $x$ and its corresponding $y$ and $k$ we can always find some $x' = 2^m x$ where $\log(2^m x + 1) - \log (2^m x)$ is sufficiently tiny such that no integer is contained in $[k\log 3 + m +\log x, k\log3 + \log(2^mx+1)]$. Note that we are implicitly using the fact that $k\log 3 + \log x$ can never be an integer.