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?

q1,q2

q0,q2

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

1 / 12 Settings

<<<>>>

Let's see a step-by-step conversion of an NFA to a DFA.

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.