# k-basis representation of natural numbers

(This is the problem 1.56 from Michael Sipser' Introduction to the theory of computation )

Let
$A_k(S)= \{ w |w \text{ is the k-basis representation}$
$\text{ without leading 0 of some natural number in the set S}\}$

Example : $A_2 (\{3,5\}) = \{11,101\}$

Let the statement $P = \exists S \text{, a set of natural number where} A_2(S) \text{ is regular and }A_3(S) \text{ isn't.}$

Is $P$ true ?

I think that $P$ is false.

Let's consider two case :

$S$ is finite :

Write a (possibly very long) regular expression which is the union of all of the k-basis representation strings of the numbers in $S$ no matter what $k$ is.

$S$ is infinite :

Construct a NFA $N$ that recognize $A_k(S)$ with :
$\text{For each symbol }e\in\Sigma\smallsetminus 0, \space$ $\delta(q_{initial},e) = q_{begin},\space q_{begin} \in F$ $\text{For each symbol }e\in\Sigma,\space \delta(q_{begin},e) = q_e ,\space \delta(q_e,\varepsilon) = q_{begin},\space q_e \in F$

Am i correct ? (I think I'm not but I'm stuck with this, maybe I don't get the definition of $A$ correctly ).

• Your solution applies only if $S$ is finite. – saadtaame May 4 '13 at 17:21
• What if the set of natural numbers is infinite? You cannot write an infinitely long regular expression. – Dave Clarke May 4 '13 at 17:22
• Yes but if $S$ is infinite then no $A_k(S)$ will be regular so it is not the set that satisfies $P$ – tumasgiu May 4 '13 at 17:27
• @tumasgiu Are you sure? $1^*$ is infinite and regular. – saadtaame May 4 '13 at 17:51
• @saadtaame Yup, I wrote too fast. – tumasgiu May 4 '13 at 18:45

Hint: For most infinite $S$, the languages $A_2(S),A_3(S)$ will both not be regular. Find some set $S$ for which $A_2(S)$ is regular (since the binary representations of numbers in $S$ are very simple), and with any luck $A_3(S)$ won't be regular. (Don't choose $S = \mathbb{N}$ or $S = \{ ax+b : x \in \mathbb{N} \}$.)
• I'm not so sure... the relation between bases is not that off the wall. It is simple to prove that e.g. $n \equiv a \pmod{m}$ is regular on any base, for any $a$ and $m$. – vonbrand May 9 '13 at 1:54
• I was thinking of the set $S = \{ 2^k-1 : k \geq 0 \}$, for which $A_2(S) = 1*$, while $A_3(S)$ is probably not regular. – Yuval Filmus May 9 '13 at 1:58