โ Theory of Computation learning pathTheory of Computation ยท Module 3 of 10
NFA and equivalence
Nondeterminism and subset construction.
๐ Key ideas
- An NFA can have zero, one or many transitions per symbol, and epsilon moves.
- It accepts if any possible path ends in an accepting state.
- Every NFA has an equivalent DFA (subset construction); NFAs are not more powerful.
- An NFA with n states may need up to 2^n DFA states.
- 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