Library

2DFA · Regular

The fourth symbol from the end, by walking back

A one-way DFA for “the 4th symbol from the end is a 1” needs 16 states, one per possible last-four window. A two-way DFA runs to the right end marker and steps back four cells: six states. Two-way heads add no power, but they can save exponentially many states.

runb1b2b3b4yes⊢, 0, 1⊣0, 10, 10, 11
The machine as drawn — 6 states, 11 transitions.

The author’s examples, run

1000 → accept01011 → accept001000 → accept0000001011 → accept0000 → reject00011 → reject000000 → reject0000000011 → reject