Nondeterministic Finite Automata

Overview

The deterministic part of DFA means that each DFA can only do one particular thing at each step of the computation.

In a nondeterministic finite automata, this is not the case. Several choices of which state to transition to may exist.

Formally, the difference between a DFA and an NFA is that the output from the transition function of a DFA is a single state. The output from the transition function of an NFA is a set of states.

Example

This is an example of an NFA. It violates several rules of DFAs:

There are two choices when in state $q_{1}$ when we read a 1. When there are multiple options, we can choose to take either.
There is no choice when in state $q_3$ when we read a 0.
There is an "$\epsilon$ transition" out of state $q_{2}$. An epsilon transition is one we can choose to take without consuming any input.

An NFA accepts if any possible path will lead us to an accept state for a given input.

Will the above NFA accept:

101
0001
100001
11000
01010101100

How can we describe the language of this NFA?

How NFAs Compute

NFAs can be viewed as parallel machines that spawn a new thread for each choice. As soon any thread reaches an accept state, the computation halts:

An NFA can take multiple paths at each computation step

We can thus look at the execution of an NFA as a tree of computation:

The execution can be viewed as a tree where each input symbol results
in branches splitting off from it

NFAs vs. DFAs

Nondeterminism gives us a lot of flexibility when constructing automata.

The NFA below recognizes the following language:

$\{w | w\text{ contains a 1 in the third position from the end}\}$.

An NFA

Trace this NFA with inputs to see how it works:

0101111
0100
100
1
1000

It is possible to construct a DFA which recognizes this same language:

A DFA with 8 states, much more complex than the NFA above

This is the DFA with minimum states recognizing this language.

As we will prove next time, all NFAs have an equivalent DFA. This means that NFAs and DFAs are equivalent in power. To show that a language is regular, you can construct a DFA or NFA which recognizes it.

Closure of Union

We have already shown that regular languages are closed under the union operation. However, this is even easier to show by using non-determinism.

Recall that $A_{1} \cup A_{2} = \{x | x \in A_{1} \text{ or } x \in A_{2}\}$

If $A_{1}$ and $A_{2}$ are both regular, than some machine $N_{1}$ and $N_{2}$ recognize them.

We can easily construct an NFA, N as follows:

An NFA constructed from two other NFAs. We add a new start
state with epsilon transitions into the original two start states

Closure of Concatenation

Recall that $A_{1} \circ A_{2} = \{xy | x \in A_{1} \text{ and } y \in A_{2}\}$

Given two NFAs $N_{1}$ and $N_{2}$, we can construct an NFA recognizing the concatenation as follows:

An NFA constructed from two other NFAs. For the first, we replace
the accept states with non-accept states with epsilon transitions into the start state of the second.

Closure of Star

Recall that $A_{1} \ast = \{x_{1}x_{2} ... x_{k} | k \geq 0$ and each $x_{i} \in A_{1}\}$

Given an NFA $N_{1}$ which recognizes $A_{1}$, we can build an NFA which recognizes $A_{1} \ast$ as follows: