ε-NFA — 0*1*
Any run of 0s followed by any run of 1s, the empty string included.
Hopcroft 2e, §2.5
Input
The input is the empty string.
Narration
Start in state A with the empty string still to read.
Finite automaton with ε-transitionsHopcroft 2e §2.5 — ε-closures
Moves that consume no input. The machine is really in the whole ε-closure of its current set of states at every moment.
This machine2 states
- Q
- {A, B}
- Σ
- {0, 1}
- q₀
- A
- F
- {B}
- |δ|
- 3 transitions
How to read the run
- The run alternates: read a symbol, then take the ε-closure.
- The closure is shown as its own step, because it is the half that gets forgotten in exams.
- The empty string can be accepted without reading anything, if the closure of the start state contains an accepting state.
Run many strings
One string per line. A blank line means the empty string.