NFA — even 0s, or ending in 1
Strings with an even number of 0s, or strings ending in 1.
Constructed — illustrates §2.3
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 e0 with "0011" 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
- {e0, e1, f}
- Σ
- {0, 1}
- q₀
- e0
- F
- {e0, f}
- |δ|
- 6 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.