Library

DFA · Regular

An a in every odd position

Positions 1, 3, 5, … must hold a; the others may hold anything. The machine only needs to know whether the next position is odd or even.

oddevenaa, b
The machine as drawn — 2 states, 3 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptabaa → accepta → acceptaaaaaaabaa → acceptb → rejectbbaa → rejectba → rejectbaaaaaabaa → reject