3.4. NFA: Non-Deterministic Finite Automata¶
3.4.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 nondeterminism turns out to be something that we can make quite concrete. In this module, we study what it means to make an FA nondeterministic, and whether it really even matters in the end.
3.4.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.4.1 and Proof
Theorem: Given some NFA MN=(QN,Σ,δN,q0,FN), there exists a DFA MD=(QD,Σ,δD,q0,FD) such that L(MN)=L(MD).
Proof: We can use an algorithm to convert MN to MD.
QD=2QN (the powerset of QN)
FD={Q∈QD∣∃qi∈Qwithqi∈FN}
Interpretation: A state qD in MD is final if any of the states from MN in the subset that qD corresponds to is final.
δD:QD×Σ→QD
Algorithm to construct MD
The start state for MD is {q0}∪closure(q0). (“Closure” of q0 is a set of states defined as q0 plus all states reachable from q0 by λ transitions.)
While there is an edge to add (that is, while our DFA is missing a transition from δD):
Choose a state A={qi,qj,...,qk} with a missing edge for a∈Σ
Compute B=δ∗(qi,a)∪δ∗(qj,a)∪…∪δ∗(qk,a)
Add state B to MD if it doesn’t already exist
Add an edge from A to B with label a
Identify final states.
For a state in QD, if any of its base QN states are final, then it is final.
If λ∈L(MN), then make the start state final.
Intuition: Given a state in MN and a character, you can get to some subset of the states in MN. Consider that to be a state in MD. There are only so many subsets of the set of MN states: the members of the powerset of MD states.
3.4.3. NFA to DFA Conversion Example¶
3.4.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 nondeterminism, 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 to start that they add no new power in terms of new languages that can be accepted. 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.
