Library

2DFT · Regular transduction (two-way)

Sorting by passes: all a’s, then all b’s

Two passes over the input: the first prints only the a’s, the second only the b’s. The output is the input sorted — counting sort, where the transducer’s head does the counting by reading the input twice.

startasbackbsdone
The machine as drawn — 5 states, 10 transitions.

The author’s examples, run

a → accept · ab → accept · baa → accept · aaab → accept · abaaa → accept · aaabbbbbabbaaabbaaa → accept · aaaaaaabbbbbbbbb