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*.

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.

- 101
- 0001
- 100001
- 11000
- 01010101100

How can we describe the language of this NFA?

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:

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

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}\}$.

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:

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.

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:

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:

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:

Copyright © 2022 Ian Finlayson | Licensed under a Attribution-NonCommercial 4.0 International License.