Library

DFA · Regular

Sipser’s M4: starts and ends with the same symbol

The first symbol picks one of two separate halves of the machine, and each half then remembers only whether the last symbol matched the first. Nothing is ever shared between the halves. Compare “As many ab’s as ba’s”, which is the same language plus the empty string.

sq1r1q2r2ababbabaab
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

a → acceptaabba → acceptaa → acceptaaaaaaabba → acceptε → rejectbabba → rejectba → rejectbaaaaaabba → reject