Library

FST · Rational transduction

Run-length decoding

a2b3 becomes aabbb: each letter is followed by how many times to repeat it, here 1 to 3. The transducer remembers the letter until the count arrives and then writes it that many times — a single edge can print a string, which is what lifts an FST above a Mealy machine.

readyheldAheldBa/b/1/a, 2/aa, 3/…1/b, 2/bb, 3/…
The machine as drawn — 3 states, 8 transitions.

The author’s examples, run

1 → reject2 → rejecta1 → accept · aa2 → accept · aaa1a1 → accept · aab1b3a3b2 → accept · bbbbaaabb