Regular grammar → NFA
Each variable becomes a state and each production becomes a move.
Beyond the prescribed text — see docs/citations.md
S → 0S | 1S | 0A A → 1B B → ε
Result · NFA
Working
| # | Head | Body |
|---|---|---|
| 1 | S | 0S |
| 2 | S | 1S |
| 3 | S | 0A |
| 4 | A | 1B |
| 5 | B | ε |
Each variable becomes a state, starting at S. Each production becomes a move.
The answer appears at the last step. if you would rather read it than watch it.
How to read itBeyond the prescribed text — see docs/citations.md
- A → aB reads a and moves to B. A → a reads a and finishes. A → ε makes A accepting.
- A right-linear grammar and an NFA are the same object written two ways.
- This topic is not in Hopcroft 2e and is not examined on this course — it is here as enrichment.