3.3. NFA: Non-Deterministic Finite Automata¶
3.3.1. Non-Deterministic Finite Automata¶
We often 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 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: Here is 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 as the 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. Since the collection of DFAs can accept exactly the same languages as the class of NFAs, we say that these two are equivalent.
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. (And sometimes non-determinism makes a functional difference in other contexts.) 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. And fourth, non-determinism is a useful concept to help simplify other concepts that we will cover later. A good example will be the study of so-called NP-Complete problems (where NP stands for nondeterministic polynomial).
