 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2005/calculus-linear-algebra-discrete-mathematics-logic-and-proof-and-models-of-computation/9/a/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

L is regular ⟺ L 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.

 New to topics? Read the docs here!