nfa-to-dfa

Converting NFAs to DFAs

fa

• This can be achieved
• $ϵ\text{-closure}(n)$ = the set of NFA states reachable from NFA state $n$ by zero or more $ϵ$ transitions.
• Steps
  1. Pick the $N_0$ with its closure, create a “super-set” $D_0$.
  2. For each character in the alphabet, find the set of NFA states that can be reached from the super-set $D_0$.
  3. Also include the closures, to form a new super-set.
  4. If the super-set is not in the list, add it to the list. The super-sets can be merged.