<p>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&lt;1$.</p>

<p>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.</p>

<p>If $1$ was written, then the transducer is again wrong, since $0$ will follow in $1^{n+1}0$.</p>

<p>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.</p>

<p>This proof has some nuances that need to be taken care of, but the ideas are there. </p>

CC BY-SA 3.0
2013-03-08T02:58:43.763Z
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?
Eric O. Lebigot
CC BY-SA 3.0
2013-03-08T06:18:54.650Z
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.
Shaull
CC BY-SA 3.0
2013-03-07T15:07:05.440Z
2013-03-08T03:57:22.213Z
2013-03-08T03:57:22.213Z
Shaull
<p>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.</p>

<p>(added) The fact that regular languages are closed under FST is a consequence of <em>Nivat's Theorem</em>. 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.</p>

CC BY-SA 3.0
2013-03-11T03:49:02.713Z
Thank you. Does this property hold true for *non-deterministic* Finite State Transducers?
Eric O. Lebigot
CC BY-SA 3.0
2013-03-11T07:49:19.987Z
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.
Hendrik Jan
CC BY-SA 3.0
2013-03-12T06:57:47.510Z
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.)
Eric O. Lebigot
CC BY-SA 3.0
2013-03-12T11:02:50.043Z
@EOL you are right, I will edit and swap $g,h$.
Hendrik Jan
CC BY-SA 3.0
2013-03-09T12:00:13.763Z
2013-03-12T11:03:15.690Z
2013-03-12T11:03:15.690Z
Hendrik Jan
<p>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.)</p>

CC BY-SA 3.0
2013-03-07T13:31:13.220Z
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?)
Shaull
CC BY-SA 3.0
2013-03-07T14:47:45.867Z
The finite state transducers I had in mind are those of Wikipedia (http://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*?
Eric O. Lebigot
CC BY-SA 3.0
2013-03-07T15:22:32.747Z
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.
Marzio De Biasi
CC BY-SA 3.0
2013-03-07T17:20:09.677Z
No, it has finite memory and can't count, to sort even a binary string you need to count.
Kaveh
<automata-theory><sorting>
Finite state transducer that sorts
Eric O. Lebigot
# Finite state transducer that sorts

(Asked by: username_0 on 2013-03-07)

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.)

**Tags:** automata-theory, sorting

> **Comments:**
> **username_1**: 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?)  
> **username_0**: The finite state transducers I had in mind are those of Wikipedia (http://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*?  
> **username_2**: Just an additional note to username_1'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.  
> **username_3**: No, it has finite memory and can't count, to sort even a binary string you need to count.  

---

## 2 answers

### Answer by username_4 on 2013-03-09. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you. Does this property hold true for *non-deterministic* Finite State Transducers?  
> **username_4**: 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.  
> **username_0**: 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.)  
> **username_4**: @EOL you are right, I will edit and swap $g,h$.  

---

### Answer by username_1 on 2013-03-07. Score: 6

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  

---

