3.3. NFA: Non-Deterministic Finite Automata¶
3.3.1. Non-Deterministic Finite Automata¶
Lots of times we have to make decisions. Sometimes, once we make the decision, we cannot undo it. Sometimes, we can go back, change our minds, make the other choice. But even then, we still had to spend the time investigating the false path.
Imagine that when we came to a decision point, we could clone ourselves, follow both paths, and then just “become” the version that turns out to be the better choice. Wouldn’t that be a hugely powerful upgrade to our lives?
That gets into some pretty complicated philosophy in real life. But in the world of Finite Automata, the concept of non-determinism turns out to be something that we can make quite concrete. In this module, we study what it means to make an FA non-deterministic, and whether it really even matters in the end.
3.3.2. NFA vs. DFA: Which is more powerful?¶
Now we are ready for the main event: Proving that every NFA can be converted to a DFA, and therefore the two machine types are equally powerful. We do this using Proof by Construction: We have an algorithm that converts any NFA to an equivalent DFA.
Theorem 3.3.1 and Proof
Theorem: Given some NFA \(M_N = (Q_N, \Sigma, \delta_N, q_0, F_N)\), there exists a DFA \(M_D = (Q_D, \Sigma, \delta_D, q_0, F_D)\) such that \(L(M_N) = L(M_D)\).
Proof: We can use an algorithm to convert \(M_N\) to \(M_D\).
\(Q_D = 2^{Q_N}\) (the powerset of \(Q_N\))
\(F_D = \{Q\in Q_D \mid \exists q_i \in Q\ \mathrm{with}\ q_i \in F_N \}\)
Interpretation: A state \(q_D\) in \(M_D\) is final if any of the states from \(M_N\) in the subset that \(q_D\) corresponds to is final.
\(\delta_D : Q_D \times \Sigma \rightarrow Q_D\)
Algorithm to construct \(M_D\)
The start state for \(M_D\) is \(\{q_0\} \cup \mathrm{closure}(q_0)\). (“Closure” of \(q_0\) is a set of states defined as \(q_0\) plus all states reachable from \(q_0\) by \(\lambda\) transitions.) Add this this state to $Q_D$.
While there is an edge to add (that is, while our DFA is missing a transition from \(\delta_D\)):
Choose a state \(A = \{q_i, q_j, ..., q_k\}\) from $Q_D$ with a missing edge for \(a \in \Sigma\)
Compute \(B = \delta^{*}(q_i, a) \cup \delta^{*}(q_j, a) \cup \ldots \cup \delta^{*}(q_k, a)\)
Add state \(B\) to \(M_D\) if it doesn’t already exist
Add an edge from \(A\) to \(B\) with label \(a\)
Identify final states.
For a state in \(Q_D\), if any of its base \(Q_N\) states are final, then it is final.
If \(\lambda \in L(M_N)\), then make the start state final.
Intuition: Given a state in \(M_N\) and a character, you can get to some subset of the states in \(M_N\). Consider that to be a state in \(M_D\). There are only so many subsets of the set of \(M_N\) states: the members of the powerset of \(M_D\) states.
3.3.4. Conclusions¶
Adding the non-determinism capability to DFAs does not result in any new capability to accept languages. The set of languages that can be accepted by a NFA is exactly the same set of languages that can be accepted by a DFA. We proved this constructively: Every DFA is automatically an NFA without non-determinism, so DFAs obviously cannnot accept languages that NFAs cannot. And any NFA can be converted using an algorithm to a DFA. So NFAs cannot accept languages that DFAs cannot.
So, is the NFA a useful concept? Why introduce them at all? First, it was not obvious at the start that they add no new power in terms of new languages that can be accepted. So, we had to work through that to convince ourselves that it is true. Second, NFAs tend to be “simpler” to understand than the equivalent DFA. See the result of the conversion example, and decide for yourself which one is easier for you to deduce the corresponding language. Or, try writing the DFA for the language from scratch as a DFA. Third, we will introduce some other conversion algorithms over the course of the semester that are easier to understand if the target is a NFA instead of a DFA.
