Library

DFA · Regular

Once bb, never aa

Two patterns in sequence: aa is allowed until the first bb, and forbidden from then on. The machine runs a search for bb, and when it finds it switches into a second machine that forbids aa — the order of events, remembered by which half of the diagram the run is in.

prepreBpostpostAababbab
The machine as drawn — 4 states, 7 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptaabba → accepta → acceptaaaaaaabba → acceptaabbaa → rejectaaaaaaabbaa → rejectbbaa → rejectabbaa → reject