Define a NFA (or NDFA) 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\))

<<Hmmm… How is this different from a DFA?>>

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.

Hopefully this one is easy to understand: Two disjoint paths, effectively giving us the union of two languages: \(L =\) << ?? >>.

\(L = \{(ab)^n \mid n>0\} \cup \{a^nb \mid n>0\}\).

Definition: \(q_j \in {\delta}^{*}(q_i,w)\) if/only if there exists some walk from \(q_i\) to \(q_j\) labeled \(w\).

For an NFA \(M\), \(L(M)= \{w \in {\Sigma}^{*} \mid \delta^{*}(q_0,w) \cap F \neq \emptyset \}\). << What does this mean? >>

NFA accepts a string if it completes processing in a final state. However for an NFA, the string is accepted if any processing path gets us to end in a final state. 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.

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.

Hypothesis: Nondeterminism allows us to accept more languages.

Can this NFA be converted to a DFA?

Does non-determinism increase the collection of languages that can be accepted? That is, can any language be accepted by an NFA that has no DFA that accepts it?

Here is a bit of intution that might give some insight:

• Nondeterminism gives branches. If we are trying to create a non-determinism simulator in a computer, we can simulate it by alternating between all of the branches, pushing each branch forward by a step. This will eventually terminate.

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

We can use an algorithm to convert \(M_N\) to \(M_D\).

• \(Q_D = 2^{Q_N}\) << What does this mean? How big is this set of states? >>

  [Right here, this is what I consider the key insight. Given a state in \(M_N\) and a symbol \(\in \Sigma\), you can get to some subset of the states in \(M_N\). Consider THAT to be a state in \(M_D\).]

• \(F_D = \{Q\in Q_D \mid \exists\ q_i \in Q\) with \(q_i \in F_N \}\) << What does this mean?? >>

• \(\delta_D : Q_D \times \Sigma \rightarrow Q_D\) << What does this mean?? >>

  Of course this begs the question: HOW?

1. Start state is \(\{q_0\} \cup \mathrm{closure}(q_0)\)

   What does \(\mathrm{closure}(q)\) mean?

   The set of states reachable from \(q\) with \(\lambda\) transitions.

1. Start state is \(\{q_0\} \cup \mathrm{closure}(q_0)\)

2. While missing a transition in \(\delta_D\):

   1. Choose a state \(A = \{q_i, q_j, ..., q_k\}\) with missing edge for \(a \in \Sigma\)

   2. Compute \(B = \delta^{*}(q_i, a) \cup \delta^{*}(q_j, a) \cup \ldots \cup \delta^{*}(q_k, a)\)

   3. Add state \(B\) if it doesn’t exist

   4. Add edge from \(A\) to \(B\) with label \(a\)

3. Identify final states

4. If \(\lambda \in L(M_N)\), then make the start state final.

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.

• NFA tend to be “smaller” and “simpler” than the equivalent DFA. (At least morphologically, but perhaps the language of a NFA is hard to grasp.)

• We will see times when it is easier to see a conversion from something to a NFA, and we know that this can always be converted in turn to a DFA.