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.