โ† Theory of Computation learning path
Theory of Computation ยท Module 3 of 10

NFA and equivalence

Nondeterminism and subset construction.

๐Ÿ“– Key ideas

  1. An NFA can have zero, one or many transitions per symbol, and epsilon moves.
  2. It accepts if any possible path ends in an accepting state.
  3. Every NFA has an equivalent DFA (subset construction); NFAs are not more powerful.
  4. An NFA with n states may need up to 2^n DFA states.
  5. NFAs are often easier to design, then converted.
๐Ÿ’ก Real-life example: An NFA is like exploring a maze with clones: at every fork a clone takes each path, and you succeed if any clone reaches the exit.
NFANondeterministic finite automaton
Epsilon transitionMove without reading a symbol
Subset constructionConverts an NFA to a DFA
Epsilon closureStates reachable by epsilon moves alone