L
is a language accepted by a nondeterministic finite automaton, then a deterministic finite automaton exists accepting L
.
The proof of this theorem is a constructive one. Given a NDFA we construct an equivalent DFA where the set of final states is the set of subsets that contains at least one final state of the starting NDFA and the transition function is defined by applying the
delta
of the NDFA to each state in a given subset and taking the union of resulting states.