3
$\begingroup$

(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 ).

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

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} \}$.)

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – vonbrand May 9 '13 at 1:54
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 9 '13 at 1:58

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.