Study
CS-311 route
Unit 2 · Lesson 4 of 6 14 min

Conversion of NFA to DFA (Subset Construction)

Replace "which state am I in?" with "which states could I be in?" and the guessing disappears.

What this unit covers

Unit 2: Finite Automata

  1. 1 Deterministic Finite Automata (DFA)A machine whose only memory is the room it is standing in, and it is still useful everywhere. · 13 min
  2. 2 Design of Deterministic Finite AutomataDesigning a DFA is deciding what is worth remembering, and forgetting everything else. · 13 min
  3. 3 Nondeterministic Finite Automata (NFA and ε-NFA)Let the machine guess, follow every guess at once, and accept if any guess works out. · 13 min
  4. 4 Conversion of NFA to DFA (Subset Construction)Replace "which state am I in?" with "which states could I be in?" and the guessing disappears. · 14 min
  5. 5 Minimisation of Deterministic Finite AutomataTwo states that can never be told apart by any input are really one state wearing two name tags. · 13 min
  6. 6 Finite Automata with Output: Moore and Mealy MachinesSome machines do more than say yes or no; they talk back after every step. · 13 min