Library

2DFT · Regular transduction (two-way)

Rotate: move the first letter to the end

abc becomes bca. The head remembers the first letter in its state, prints everything after it, and prints the remembered letter on reaching the end marker. A one-way transducer cannot know where the end is without guessing; a head that sees the end marker simply knows.

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

The author’s examples, run

a → accept · ab → accept · baa → accept · aaab → accept · baaaa → accept · aaabbbbbabbaaabbaaa → accept · bbbbabbaaabbaaab