Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers are best.)
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ You should be more specific in your question. A finite state transducer outputs a letter for every letter it receives. In this case, when the first element is read, the transducer has to output the smallest number that will be read eventually. Clearly that's impossible. Perhaps define better what kind of transducer you mean (does it have memory, such as a tape?) $\endgroup$– ShaullMar 7, 2013 at 13:31
-
$\begingroup$ The finite state transducers I had in mind are those of Wikipedia (en.wikipedia.org/wiki/Finite_state_transducer). It is possible to write a (very large) finite state transducer that sorts strings of a given length on a given alphabet: each path correspond to one of the possible inputs (and the output to the sorted string). However, is there a smaller FS transducer that can do this? and that can sort for any input length? $\endgroup$– Eric O. LebigotMar 7, 2013 at 14:47
-
1$\begingroup$ Just an additional note to Shaull's good answer: if the length $k$ of the strings is fixed (not an input parameter) then you can build the minimum transducer that given a string of length $\leq k$ sorts and outputs it. $\endgroup$– Marzio De BiasiMar 7, 2013 at 15:22
-
$\begingroup$ No, it has finite memory and can't count, to sort even a binary string you need to count. $\endgroup$– KavehMar 7, 2013 at 17:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
If you allow me to give an answer that uses "technical" terminology: the output of a finite state transducer on any given regular language is again a regular language. The sort of regular $(ab)^*$ equals non-regular $\{ a^nb^n \mid n\ge 0\}$. Thus that cannot be performed by a FST.
(added) The fact that regular languages are closed under FST is a consequence of Nivat's Theorem. Every FST $T$ can be decomposed into a regular language $R$, and morphisms $g,h$ such that $T(L) = g(h^{-1}(L) \cap R)$. In short $R$ consists of "letters" of the form $(a,b)$ where $a,b$ are from the input and output alphabets respectively (or empty), and $h,g$ select the input/ output components from those pairs.
-
$\begingroup$ Thank you. Does this property hold true for non-deterministic Finite State Transducers? $\endgroup$ Mar 11, 2013 at 3:49
-
$\begingroup$ Indeed, it does hold. The fact that the output language of a FST is again regular on regular input is proven in a way similar to the intersection of regular languages. Run the automaton for the input in parallel with the FST to obtain an automaton for the output language. $\endgroup$ Mar 11, 2013 at 7:49
-
$\begingroup$ Thank you. I guess you mean $g$, $h$ select the output/input components, right? (I'm not familiar with the concepts involved, so I want to make sure I understand at least the basics.) $\endgroup$ Mar 12, 2013 at 6:57
-
$\begingroup$ @EOL you are right, I will edit and swap $g,h$. $\endgroup$ Mar 12, 2013 at 11:02
$\begingroup$
$\endgroup$
2
It is not possible to sort an arbitrary string with a fixed size transducer. For simplicity, let's say you are working over the alphabet $\{0,1\}$, where $0<1$.
Proof: assume by way of contradiction that there exists such a transducer $A$ with $n$ states. Consider the input $1^{n+1}0$. Since $A$ has $n$ states, it must repeat a state before it finishes reading $1^{n+1}$. Consider what was printed so far. If $0$ was written, then we can consider the run on $1^{n+1}$ alone: it outputs a 0 and therefore $A$ does not sort its input.
If $1$ was written, then the transducer is again wrong, since $0$ will follow in $1^{n+1}0$.
If nothing was written, then the output is the same if we remove the loop (the run from the state that was repeated, back to itself). So we get the same output for two words that differ in the number of $1's$, which is again wrong.
This proof has some nuances that need to be taken care of, but the ideas are there.
-
$\begingroup$ Thank you! However, I am stuck at the first step ("If 0 was written…"): in fact, there exists a transducer with $3 \le n$ states that correctly sorts both $1^{n+1}0$ and $1^{n+1}$ (with two final states, one for strings that end with $0$ [it starts by outputting a single 0], the other for strings that end with $1$ [it only outputs 1s]). Thus, I can't see why "the run on $1^{n+1}$ alone necessarily outputs $0$" (it does not, in the small transducer I described)… Could you elaborate on the "If 0/1 was written…" steps? $\endgroup$ Mar 8, 2013 at 2:58
-
$\begingroup$ I assumed you are using deterministic transducers. What you describe here is a nondeterministic transducer (that "guesses" whether there is a 0 at the end). Nondeterministic transducers are also unable to sort arbitrary strings, but the proof is slightly different. I think using similar argument on the word $1^{n+1}0^{n+1}$ should work, by removing cycles in both parts of the word. $\endgroup$– ShaullMar 8, 2013 at 6:18