Library

Mealy · Rational transduction

A Vigenère cipher with the key “bc”

Over the alphabet a–d, shift the 1st, 3rd, 5th … letter by 1 and the others by 2. A Caesar cipher has one state; a Vigenère cipher has one per letter of its key, because the only thing it must remember is where in the key it is.

k1k2a/b, b/c, c/d…a/c, b/d, c/a…
The machine as drawn — 2 states, 8 transitions.

The author’s examples, run

a → reject · bb → reject · caa → reject · bcab → reject · bdaaa → reject · bcbddacdcdcaaacccb → reject · abbaaaaabcbadac