patternMinor
Building a finite state transducer
Viewed 0 times
finitebuildingtransducerstate
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#2745, answer score: 5
Revisions (0)
No revisions yet.