NFA — ends in 01
Strings over {0, 1} that end in 01.
Hopcroft 2e, §2.3 (Fig. 2.9)
Input
Branch tree
Every branch the machine is exploring at once. A branch with no move left dies where it stands, and stays on the diagram so you can see where the guess went wrong.
Narration
Start in state q0 with "0101" still to read.
Nondeterministic finite automatonHopcroft 2e §2.3 — δ̂ over sets
A state may have several moves on a symbol, or none. The string is accepted if *any* branch ends in an accepting state.
This machine3 states
- Q
- {q0, q1, q2}
- Σ
- {0, 1}
- q₀
- q0
- F
- {q2}
- |δ|
- 4 transitions
How to read the run
- Every live branch is shown at once, as a tree rather than a path.
- A branch with no move dies where it stands and stays greyed on the tree, labelled with the step it died at.
- One surviving accepting branch is enough. The others dying costs nothing.
Run many strings
One string per line. A blank line means the empty string.