5
$\begingroup$

I know it's possible to build a Finite State Transducer for converting numbers from base 2 to base 4 or 8 or other powers of 2 (translating from base N to base N^M is easy). However I've never seen a FST that can convert numbers from base 1 to base 2 or viceversa. Can a FST even do this? If so, can you please give some hints on building such a FST?

$\endgroup$
  • $\begingroup$ What do you mean by base 1 ? $\endgroup$ – scaaahu Jul 15 '12 at 5:29
  • $\begingroup$ 1 in base 1 is | (let's use ones and zeros for base 2 notation and | for base 1 notation), 2 in base 1 is ||, 3 in base 1 is ||| and so on... $\endgroup$ – adrianton3 Jul 15 '12 at 5:34
5
$\begingroup$

In my opinion, such transducers does not exist.

It is not possible to convert from base 2 to base 1, since the regular language $\{10^n\ |\ n \in \mathbb{N}\}$ would become $\{1^{2^n}\ |\ n \in \mathbb{N}\}$, which is nonregular. However, regular languages are closed under the translation by the finite state transducer.

On the other hand, I was not able to find such a straightforward proof for the opposite case (that does not mean that such a proof does not exist). But I am inclined to believe that it is not possible as well. The reason is that the transducer would have some transitions writing $\varepsilon$ and some transitions writing non-$\varepsilon$ words. However, since the length of the image of $w, |w| = n$ is $O(\log n)$, the transitions writing non-$\varepsilon$ words are used significantly less (but nonconstant number of times) than the $\varepsilon$-transitions on all inputs. However, for a finite state transducer, a transition is either used a constant number of times, or there exists an input such that the number of uses of that transition is at least $\frac{1}{m} n$, where $m$ is number of transitions and $n$ is the length of the input (this is not so hard to prove). Moreover, clearly, such input exists for arbitrarily large $n$. Therefore, we get a contradiction.

$\endgroup$
  • $\begingroup$ Consider transcribing from base $a$ to base $b$ with $a < b$. Reading over $w$ from LSB to MSB, I think you can have arbitrarily late bits influencing the first bit of the output. Finite control can not handle that. $\endgroup$ – Raphael Jul 21 '12 at 18:26

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.