Library

NFA · Regular

Some letter is missing

Over a, b and c, accept the words that do not use all three letters. The NFA guesses which letter will be missing and never reads it; a DFA has to track which letters it has seen — eight subsets instead of four states.

startnoAnoBnoCb, ca, ca, bb, ca, ca, b
The machine as drawn — 4 states, 12 transitions.Every word up to length 5, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptaabba → acceptacca → acceptaabbbabbaaa → acceptcabba → rejectbcca → rejectcabbbabbaaa → rejectabc → reject