Non-Deterministic Finite Automata¶
1. NFA: Non-Deterministic Finite Automata¶
Definition:
Define a NFA as \((Q, \Sigma, \delta, q_0, F)\) where
- \(Q\) is a finite set of states
- \(\Sigma\) is the input alphabet (a finite set)
- \(q_0\) is the initial state (\(q_0 \in Q\))
- \(F \subseteq Q\) is a set of final states
- \(\delta: Q \times(\Sigma \cup \{\lambda\}) \rightarrow 2^Q\) (\(2^Q\) here means the power set of \(Q\))
The specific difference from a DFA is that, while the result of \(\delta\) for the DFA is some state \(q \in Q\), the result of \(\delta\) for the NFA is any subset of \(Q\).
Non-deterministic means that it allows choices. From a state on input \(b\), \(\delta\) might include transitions to more than one state.
Example:
Figure 1: Example of NFA
In this example, \(\delta(q_0, a) = \{q_1, q_2\}\). (So, \(\delta\) is no longer meets the mathematical definition of a function!)
Hopefully this one is easy to understand: We two disjoint paths, effectively giving us the union of two languages: \(L = \{aa\} \cup \{ab^nb \mid n \ge 0\}\).
Example:
\(L = \{(ab)^n \mid n>0\} \cup \{a^nb \mid n>0\}\).
Figure 2: Second Example of NFA: A simple "go this way or go the other way" choice.
Definition: \(q_j \in {\delta}^{*}(q_i,w)\) if and only if there exists some walk from \(q_i\) to \(q_j\) labeled \(w\).
From previous example:
\(\delta^{*}(q_0, ab) = \{q_5, q_6, q_1\}\).
\(\delta^{*}(q_0, aba) = \{q_3\}\).
Definition: For an NFA \(M\), \(L(M)= \{w \in {\Sigma}^{*} \mid \delta^{*}(q_0,w) \cap F \neq \emptyset \}\)
What does this mean? It means that the machine accepts all strings \(w\) from the set of all possible strings (generated from the alphabet \(\Sigma\)) such that the states reachable on \(w\) from the start state (\(q_0\)) is in the final state set.
Note that it does not matter that there are paths where \(w\) can go wrong. What matters is that there is at least one way for \(w\) to be right.
Why nondeterminism? It makes it easier to describe a FA. What does "easier" mean? It could mean easier to comprehend when looking at it. Or maybe easier for the developer to write it. Or maybe smaller (in terms of the number of states). Or maybe it is more efficient (but probably not because non-determinism can be expensive to simulate). From a performance point of view, to determine if a string is accepted can take a LONG time to try out all possibilities. But, all that we care about right now is existance, not performance.
2. NFA vs. DFA: Which is more powerful?¶
Consider the following NFA.
Figure 3: An NFA.
Note
Q: What language is this?
A: Alternating a's and b's, starting with a.
Can this NFA be converted to a DFA?
Yes, because here is one. Note that the names of the states are chosen to help see their relationships to the original NFA.
Figure 4: A DFA that accepts the same language.
Note
Q: Is this a proof?
A: Yes. It is a proof by construction. The theorem is of the form "There exists X". (In our case, it was written as "Does there exist a DFA that corresponds to this NFA?") The proof is of the form "Here is an example of X". (In our case, "Here is an acceptable DFA that answers the question".)
Note
Try this conversion out using JFLAP. JFLAP can convert a NFA to a DFA.
Theorem 1 and Proof
Theorem: Given an 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}\)
\(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\)
Start state is \(\{q_0\} \cup \mathrm{closure}(q_0)\) (Note that "closure" of \(q_0\) is a set of states defined as \(q_0\) plus all states reachable from \(q_0\) by \(\lambda\) transitions.
While can add an edge (that is, while missing a transition from \(\delta_D\))
- Choose a state \(A = \{q_i, q_j, ..., q_k\}\) with 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\) if it doesn't exist
- Add 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: That would be members of the powerset of \(M_D\) states.
Example:
Figure 5: Another NFA to convert
Let's begin with the start state. Closure(\(q_0\)) in \(M_N\) is \(\{q_0, q_1, q_2\}\). So this is the start state.
For example: From \(M_D\) state \(q_0,q_1,q_2\), determine the subset of states that can be reached from any of those states on letter \(a\). This would be the subset \(q_3,q_4\).
Note
Do this conversion using JFLAP. You should get the following result.
Answer:
Figure 6: Converted DFA
Conclusion: NFA adds no new capability. So why bother with the idea?
- First, it wasn't obvious that they are the same. NFA is a useful concept.
- An NFA tends to be "smaller" and "simpler" than the equivalent DFA. (At least in terms of the number of states and transition. But perhaps the language of a NFA is harder for a person to grasp.)
- Throughout the semester, we will do a lot of converting from one machine type to another. The conversion process might be easier to understand when the target is an NFA, and we know that this can always be converted in turn to a DFA.
