NFA: Nondeterministic Finite Automata

Definition

A nondeterministic finite automaton (NFA) is a tuple $M = (Q, \Sigma, \Delta, s, F)$ where:

Component	Description
$Q$	Finite set of states
$\Sigma$	Input alphabet (finite)
$\Delta \subseteq Q \times \Sigma \times Q$	Transition relation
$s \in Q$	Start state
$F \subseteq Q$	Set of accepting states

Key Feature: Nondeterminism

From a state $q$ on input $a$, there may be:

• Zero transitions: no next state
• One transition: one next state (like DFA)
• Multiple transitions: several possible next states

Extended Transition Relation

One-Step Transition

Write $q \xrightarrow{a} q'$ if $(q, a, q') \in \Delta$.

Multi-Step Transition

Define $q \xrightarrow{w} q'$ (there is a path from $q$ to $q'$ labelled by $w$) inductively:

$\frac{}{q \xrightarrow{\varepsilon} q} \qquad \frac{q \xrightarrow{a} q'' \quad q'' \xrightarrow{w} q'}{q \xrightarrow{aw} q'}$

Language

The NFA accepts string $w$ if there exists an accepting state reachable from the start:

$w \in L(M) \iff \exists q_f \in F. s \xrightarrow{w} q_f$

Example: Contains “ab”

NFA that accepts strings over $\{a, b\}$ containing substring “ab”:

• $Q = \{q_0, q_1, q_2\}$
• Transitions:
  • $q_0 \xrightarrow{a} q_0$, $q_0 \xrightarrow{b} q_0$ (stay in $q_0$ until we see ‘a’)
  • $q_0 \xrightarrow{a} q_1$ (transition to $q_1$ if we see ‘a’)
  • $q_1 \xrightarrow{b} q_2$ (transition to accepting on ‘b’)
  • $q_2 \xrightarrow{a} q_2$, $q_2 \xrightarrow{b} q_2$ (stay accepting)
• $s = q_0$, $F = \{q_2\}$

Example: Ends with “ab”

NFA that accepts strings ending in “ab”:

• $Q = \{q_0, q_1, q_2\}$
• Transitions:
  • $q_0 \xrightarrow{a} q_0$, $q_0 \xrightarrow{b} q_1$
  • $q_1 \xrightarrow{a} q_2$, $q_1 \xrightarrow{b} q_1$
  • $q_2 \xrightarrow{a} q_0$, $q_2 \xrightarrow{b} q_1$
• Or: more standard construction with $q_0 \xrightarrow{a,b} q_0$, plus $q_0 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_2$
• $s = q_0$, $F = \{q_2\}$

Non-acceptance

An NFA rejects string $w$ if:

• No path from $s$ reaches any accepting state on input $w$, OR
• The computation “gets stuck” (no valid transition)

Note: Nondeterminism means existential acceptance — if ANY path reaches accepting, the string is accepted.

Size and Complexity

• Number of states: $|Q|$
• Number of transitions: $|\Delta|$
• For each state-symbol pair, potentially $|Q|$ outgoing transitions

---

Summary

• NFA: $(Q, \Sigma, \Delta, s, F)$ with nondeterministic transition relation
• A string is accepted if SOME path reaches an accepting state
• Multiple transitions from a state on the same symbol allowed
• No transition on a symbol means that path dies