# Building a finite state transducer

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?

• What do you mean by base 1 ? – scaaahu Jul 15 '12 at 5:29
• 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... – adrianton3 Jul 15 '12 at 5:34

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.

• 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. – Raphael Jul 21 '12 at 18:26