[Solved]: Building a finite state transducer

Problem Detail: 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?

Asked By : adrianton3

Answered By : 042

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2745  Ask a Question  Download Related Notes/Documents

Leave a Reply