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\)