NFA and DFA Examples

Example 1: Contains “aaa”

NFA

NFA accepting strings over $\{a, b\}$ containing three consecutive $a$‘s:

• $Q = \{q_0, q_1, q_2, q_3\}$
• Transitions:
  • $q_0 \xrightarrow{a,b} q_0$ (stay until we start counting)
  • $q_0 \xrightarrow{a} q_1$ (first $a$)
  • $q_1 \xrightarrow{a} q_2$ (second $a$)
  • $q_2 \xrightarrow{a} q_3$ (third $a$, accept)
  • $q_3 \xrightarrow{a,b} q_3$ (stay accepting)
• $F = \{q_3\}$

DFA Equivalent

Via subset construction, the DFA has up to $2^4 = 16$ states, but many are unreachable.

Example 2: Contains “ab” as Substring

NFA

Intuitively: stay in $q_0$, transition to $q_1$ on $a$, then to $q_2$ on $b$, stay in $q_2$.

DFA

• $Q = \{q_0, q_1, q_2\}$
• Transitions:

State	$a$	$b$
$q_0$	$q_1$	$q_0$
$q_1$	$q_1$	$q_2$
$q_2$	$q_2$	$q_2$

$F = \{q_2\}$

Example 3: Modulo Counter

DFA: Divisible by 4 (Binary)

Accepts binary strings divisible by 4:

• $Q = \{q_0, q_1, q_2, q_3\}$ (remainder mod 4)
• $\delta(q_r, 0) = q_{(2r) \bmod 4}$
• $\delta(q_r, 1) = q_{(2r+1) \bmod 4}$
• $F = \{q_0\}$

Intuition

Reading binary left-to-right:

• Append 0: multiply by 2
• Append 1: multiply by 2, add 1

Example 4: Exact Pattern

DFA: Exactly “ab”

• $Q = \{q_0, q_1, q_2, q_d\}$
• Transitions:

State	$a$	$b$
$q_0$	$q_1$	$q_d$
$q_1$	$q_d$	$q_2$
$q_2$	$q_d$	$q_d$
$q_d$	$q_d$	$q_d$

$F = \{q_2\}$

Dead state $q_d$ ensures no other strings are accepted.

Example 5: At Most Two $a$‘s

DFA

Accepts strings with at most two $a$‘s:

• $Q = \{q_0, q_1, q_2, q_3\}$
• States track how many $a$‘s seen so far
• $q_i$: seen exactly $i$ $a$‘s
• $q_3$: seen three or more $a$‘s (rejecting trap)

State	$a$	$b$
$q_0$	$q_1$	$q_0$
$q_1$	$q_2$	$q_1$
$q_2$	$q_3$	$q_2$
$q_3$	$q_3$	$q_3$

$F = \{q_0, q_1, q_2\}$

Example 6: Union via NFA-$\varepsilon$

Languages

$L_1 = \{w : w \text{ ends in } a\}$

$L_2 = \{w : w \text{ ends in } b\}$

NFA-$\varepsilon$ for $L_1 \cup L_2$

Create new start with $\varepsilon$-transitions to both machines:

Accepting: both $F_1$ and $F_2$.

---

Summary

• NFAs are easier to construct for pattern detection
• DFAs are canonical (unique minimal DFA)
• Union uses epsilon transitions in NFAs
• Counting/modulo uses state to track remainder