Deterministic Finite Automata (DFA)

A DFA is a 5-tuple M = (Q, Σ, δ, q₀, F):

  • Q: finite set of states
  • Σ: input alphabet
  • δ: Q × Σ → Q, the transition function (exactly one move per state and symbol)
  • q₀ ∈ Q: start state
  • F ⊆ Q: set of final (accepting) states

A string is accepted if, after reading all of it, the DFA is in a final state.

Example: Strings over {0, 1} Ending in "01"

Text
Transition table (→ start, * final)

  State  |  0   |  1
 --------+------+------
  → q0   |  q1  |  q0
    q1   |  q1  |  q2
  * q2   |  q1  |  q0

q0: haven't seen a useful suffix     q1: last symbol was 0     q2: last two symbols were 01
100101startq0q1q2
DFA accepting binary strings that end in 01 (double circle = final state)

Tracing the input 1101

Text
δ(q0, 1) = q0 → δ(q0, 1) = q0 → δ(q0, 0) = q1 → δ(q1, 1) = q2
q2 ∈ F  ⇒  1101 is ACCEPTED

Simulating the DFA in C

C
#include <stdio.h>
int main() {
    int delta[3][2] = { {1, 0}, {1, 2}, {1, 0} };   // [state][symbol]
    const char *tests[] = {"1101", "0110", "01", "1"};
    for (int t = 0; t < 4; t++) {
        int q = 0;
        for (const char *p = tests[t]; *p; p++) q = delta[q][*p - '0'];
        printf("%-5s -> %s\n", tests[t], q == 2 ? "Accepted" : "Rejected");
    }
}
1101 -> Accepted 0110 -> Rejected 01 -> Accepted 1 -> Rejected

DFA Minimization (Partition Method)

  1. Remove unreachable states.
  2. Start with two groups: final states and non-final states.
  3. Split any group whose states go to different groups on some input.
  4. Repeat until no group splits. Each group becomes one state.
Myhill–NerodeThe minimal DFA for a regular language is unique (up to renaming of states).
Track your progress through the Theory of Computation course