1.Non-Deterministic Finite Acceptor (1)§

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?>>

Non-Deterministic Finite Acceptor (2)

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

Transitions to a null subset is a failed path.

Non-deterministic means that it allows choices. From a state on input \(b\), \(\delta\) might include transitions to more than one state.

Another difference:

We allow \(\lambda\) transitions (a free ride to another state).

NFA Example 1

In this example, \(\delta(q_0, a) =\) << ?? >>.

(So, \(\delta\) is no longer meets the mathematical definition of a function!)

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

NFA Example 2

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

A simple “go this way or go the other way”.

Unfortunately, they are not always so simple to understand!

Accepting a String

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

From previous example:

\(\delta^{*}(q_0, ab) =\) << ?? >>.

\(\delta^{*}(q_0, aba) =\) << ?? >>.

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.

Why nondeterminism?

It makes it “easier” to describe a FA.

<< What might “easier” mean? >>

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.

Which is more powerful?

Can this NFA be converted to a DFA?

Key Question

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.

Key Theorem

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

Class(DFA) == Class(NFA) Proof

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?

Algorithm to construct \(M_D\) (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.

Algorithm to construct \(M_D\) (2)

Start state is \(\{q_0\} \cup \mathrm{closure}(q_0)\)
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\)
Identify final states
If \(\lambda \in L(M_N)\), then make the start state final.

Example: NFA to DFA

Settings

Saving...

Server Error
Resubmit

So, why NFA?

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.