Library

DFA · Regular

The third symbol from the end is a 1

An NFA guesses where the end is and needs four states. A DFA cannot guess: it must remember the last three symbols, all eight combinations of them. This is the language family where determinising costs 2ⁿ.

Recognises the same language as The third symbol from the end is a 1, by guessing, which was listed first.

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

The author’s examples, run

100 → accept0110 → accept00100 → accept0000000110 → accept000 → reject0010 → reject00000 → reject0000000010 → reject