DFA — contains 01
Strings over {0, 1} that contain 01 as a substring.
Hopcroft 2e, §2.2 (Example 2.1)
Input
Narration
Start in state q0 with "0110" still to read.
Deterministic finite automatonHopcroft 2e §2.2 — δ̂
Exactly one move per state and symbol, so a run is a single path. The string is accepted if that path ends in an accepting state.
This machine3 states
- Q
- {q0, q1, q2}
- Σ
- {0, 1}
- q₀
- q0
- F
- {q2}
- |δ|
- 6 transitions
How to read the run
- One state is current at a time; it is outlined in blue.
- The transition just taken is drawn in blue, and the symbol just read is boxed.
- If a state has no move on the next symbol, the run dies there and the string is rejected — that is the implicit dead state a textbook diagram leaves off.
Run many strings
One string per line. A blank line means the empty string.