Lecture 7: Non-deterministic vs Deterministic Finite Automata

The following theorem shows that deterministic and non-deterministic finite automata accept the same class of languages.

Theorem: For every non-deterministic finite automaton $N$, there exists a deterministic finite automaton $M$ that accepts the same language, $L(M)=L(N)$.

Proof: The idea is to have states in $M$ that correspond to subsets of states in $N$. Let $Q_N$ be the states of $N$. We want that for every word $w\in\Sigma^\ast$, the automaton $M$ is in the following state after reading $w$, $$\delta_M^\ast(w) = \{ q\in Q_N \mid \text{$N$ has a computation path for the word $w$ that ends in the state $q$} \}.$$ If we have an automaton $M$ with this property, then it has the same language as $N$ if we choose the accept states of $M$ as $$F_M = \{ Q \subseteq Q_N \mid \text{$Q$ contains an accept state of $N$} \}.$$ Let $q_0$ be the start state of $N$. As start state for $M$, we choose $$Q_0=\{ q\in Q_N \mid \text{$q$ can be reached from $q_0$ by $\varepsilon$-transitions} \}.$$ Finally, the transition function of $M$ is defined as $$\begin{aligned} \delta_M(Q,x) = \{q\in Q_N\mid &\text{$q$ can be reached from a state in $Q$ by $\varepsilon$-transitions }\\ \qquad \qquad \qquad&\text{and exactly one $x$-transition} \}. \end{aligned}$$ With this transition function and start state, the repeated transition function $\delta_M^\ast$ indeed has the property above (proof by induction). Therefore, $$\begin{aligned} w \in L(M) \Leftrightarrow& \delta_M^\ast(w)\in F_M\\ \Leftrightarrow & \text{$N$ has a computation for $w$ that ends in an accept state of $N$}\\ \Leftrightarrow & w\in L(N). \end{aligned}$$ $\square$