Conversions

The heart of the exam. Each of these is a mechanical procedure whose intermediate working a textbook prints only as a finished answer — here you can step through it and read what each step did.

Finite automata and regular expressions

• NFA → DFAThe subset construction: every set of NFA states the machine could be in becomes one DFA state.Hopcroft 2e, §2.3.5 (and §2.5.5 for an ε-NFA)
• ε-NFA → NFARemove ε-transitions by giving every state the moves its ε-closure allows.Hopcroft 2e, §2.5.3
• Minimise a DFATable filling: mark every distinguishable pair, then merge what is left.Hopcroft 2e, §4.4.1 and §4.4.3
• DFA → regular expressionState elimination: rip out one state at a time, relabelling the paths that went through it.Hopcroft 2e, §3.2.2
• Regular expression → ε-NFAThompson's construction, one parse-tree node at a time, bottom-up.Hopcroft 2e, §3.2.3
• Regular grammar → NFAbeyond the syllabusEach variable becomes a state and each production becomes a move.Beyond the prescribed text — see docs/citations.md

Pushdown automata

• Final state ↔ empty stackThe two PDA acceptance modes, interconverted — the bottom marker, the drain state and the detecting ε-moves, one step at a time.Hopcroft 2e, §6.2.3–6.2.4 (Thms 6.9 and 6.11)
• Grammar → PDAThe one-state construction: productions become expansion moves, terminals become match moves, and the stack holds the leftmost derivation.Hopcroft 2e, §6.3.1 (Thm 6.13)