Library

ε-NFA · Regular

An even number of a’s, or an odd number of b’s

Union by ε: the start state jumps silently into two separate machines, one counting a’s and one counting b’s, and the word is accepted if either ends in an accepting state. Each half ignores the other’s letter.

startevenAevenBoddAoddBεεaabbbbaa
The machine as drawn — 5 states, 10 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptbaabb → acceptb → acceptaaaaaaabba → accepta → rejectaaabb → rejectaaaaaabba → rejectaabba → reject