= Solution
A <regular language> over a finite <alphabet> is a <formal language> recognized by a <deterministic finite automaton>; equivalently it is described by a <regular expression>. A <nondeterministic finite automaton> accepts an input <string> if at least one permitted computation consumes that <string> and reaches an accepting state. The connection is the equivalence
$$
\boxed{L\text{ is regular}\iff L\text{ is recognized by some nondeterministic finite automaton}.}
$$
Every <deterministic finite automaton> is a special case of a <nondeterministic finite automaton>. Conversely, the <subset construction> makes a <deterministic finite automaton> whose states record the <set> of all possible current states of a <nondeterministic finite automaton>. After each input symbol, update that <set> by taking all permitted transitions, also including any <epsilon closure>. A new state is accepting exactly when it contains an old accepting state. A finite state <set> has finitely many <subsets>, so this really is a <deterministic finite automaton> recognizing the same <formal language>.
Back to article page
