I. Definition

A nondeterministic finite automaton has the ability to be in several states at once.

Transitions from a state on an input symbol can be to any set of states.

• Start in one start state.
• Accept if any sequence of choices leads to a final state.
  • “Can” go to final state
• Intuitively: the NFA always “guesses right.”
  • Won’t choose wrong branches

1. Formal NFA

The only difference between an NFA and a DFA is in the type of value that $\delta$ returns:

a set of states in the case of an NFA and a single state in the case of a DFA.

$$ A = (Q,\Sigma, \delta, q_0, F) $$

where:

1. $Q$ is a finite set of states
2. $\Sigma$ is a finite set of input symbols
3. $q_0$, a member of $Q$, is the start state
4. $F$, a subset of $Q$, is the set of final (or accepting) states
5. $\delta$, the transition function, returns a set of states

2. Language

A string w is accepted by an NFA if $δ(q_0, w)$ contains at least one final state.

The language of the NFA is the set of strings it accepts.

3. Equivalence of DFA’s and NFA’s

Can be proved by Subset Construction

NFA = $( Q, \Sigma, \delta_N, q_0, F )$, construct equivalent DFA with:

• States $2^Q$ (Set of subsets of Q).
• Inputs $Σ$.