DFA: Deterministic Finite Automata

Definition

A deterministic finite automaton (DFA) is a tuple $M = (Q, \Sigma, \delta, s, F)$ where:

Component	Description
$Q$	Finite set of states
$\Sigma$	Input alphabet (finite)
$\delta : Q \times \Sigma \to Q$	Transition function
$s \in Q$	Start state
$F \subseteq Q$	Accepting states

Key Feature: Determinism

For every state $q$ and symbol $a$, there is exactly one next state $\delta(q, a)$.

• No ambiguity
• No “stuck” states (unless $\delta$ is partial)
• Exactly one computation path for each input

Extended Transition Function

Definition

Extend $\delta : Q \times \Sigma \to Q$ to $\hat{\delta} : Q \times \Sigma^* \to Q$:

$\hat{\delta}(q, \varepsilon) = q$ $\hat{\delta}(q, aw) = \hat{\delta}(\delta(q, a), w)$

Language

$w \in L(M) \iff \hat{\delta}(s, w) \in F$

The string is accepted iff the unique computation path ends in an accepting state.

Example: Divisible by 3

DFA over $\{0, 1, 2\}$ accepting numbers whose digit sum is divisible by 3:

• $Q = \{q_0, q_1, q_2\}$ (remainder mod 3)
• $\delta(q_i, d) = q_{(i+d) \bmod 3}$
• $s = q_0$, $F = \{q_0\}$

Example: Even Parity

DFA over $\{0, 1\}$ accepting strings with an even number of 1s:

• $Q = \{q_0, q_1\}$ (parity of seen 1s)
• $\delta(q_0, 0) = q_0$, $\delta(q_0, 1) = q_1$
• $\delta(q_1, 0) = q_1$, $\delta(q_1, 1) = q_0$
• $s = q_0$, $F = \{q_0\}$

Example: Ends with “ab”

DFA over $\{a, b\}$ accepting strings ending in “ab”:

• $Q = \{q_0, q_1, q_2, q_d\}$
• Transitions (key ones):
  • $q_0$: last char is $b$ (or start)
  • $q_1$: last char is $a$
  • $q_2$: last two chars are $ab$
  • $q_d$: dead state (or integrate below)
• More commonly: $Q = \{q_0, q_1, q_2\}$ with careful transitions

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

$F = \{q_2\}$

Complete vs Partial DFAs

Complete DFA

$\delta$ is total: there is exactly one transition for every $(q, a) \in Q \times \Sigma$.

Every input has a unique complete computation.

Partial DFA

$\delta$ may be undefined for some $(q, a)$.

If computation reaches an undefined transition, the string is rejected.

Conversion

Any partial DFA can be converted to a complete DFA by adding a “trap” or “dead” state.

Rejection

A DFA rejects string $w$ if:

$\hat{\delta}(s, w) \notin F$

The computation exists (deterministically) but ends in a non-accepting state.

State Diagram Convention

• Circles represent states
• Double circles represent accepting states
• Arrow from “start” marks the start state
• Labelled arrows between states show transitions

---

Summary

• DFA: $(Q, \Sigma, \delta, s, F)$ with deterministic transition function
• Exactly one computation path per input
• Accept iff final state is in $F$
• Complete vs partial: complete has all transitions defined