Library

DFA · Regular

Roman numerals from I to MMMCMXCIX

Every well-formed Roman numeral from 1 to 3999. Hundreds, tens and units each follow one pattern — I, II, III, IV, V … IX — so the minimal DFA is the same five-state gadget three times, after a short run of M’s. Each gadget has a “done” state: IV, IX and III all leave nothing more to say in that place.

startIVXLCDMIII✓VIXXX✓LXCCC✓DCMMMMM
The machine as drawn — 19 states, 75 transitions.

The author’s examples, run

IV → acceptXIX → acceptXLII → acceptMCMXCIV → acceptMMMCMXCIX → acceptIIII → rejectIC → rejectVX → rejectMMMM → reject