Cs374 Lecture 6

NFA -> DFA conversion.

NFA can be converted to DFA because there are a finite number of states/edges in NFA.

Given NFA M = (Q, \Sigma, s, \delta, A), create DFA M' = (Q^', ..) where Q^' = 2^Q s^' = {\epsilon - reach(s)} \delta^' (S, a) = \Cup_{q \in S} \delta^*(q,a)

This construction is called subset construction/power set construction)