Theory of computation

DFA

Suppose we want to build a machine that decides whether a given string belongs to some regular language. Example language:

All strings over {a, b} that end with "ab"

• "aab" ✅
• "abb" ❌
• "xxab" (if x not in alphabet, invalid) ❌

We want a mechanical method that scans characters one by one and says “yes, it’s in the language” or “no, it’s not”.

A Deterministic Finite Automaton (DFA) is the simplest such machine.

It has:

1. States (Q): finite memory slots. Think of them as “modes of being.”
2. Alphabet (Σ): the allowed symbols, e.g., {a, b}.
3. Transition function (δ): rules for moving between states when reading a symbol.
4. Start state (q₀): where you begin.
5. Accept states (F): if you stop here after reading the whole string, you say “accept”.

How DFA Works

• Input is read left to right, one character at a time.
• At each step, the machine:
  • looks at its current state,
  • looks at the current symbol,
  • moves to a new state (determined uniquely — deterministic).
• After the input ends:
  • If the machine is in an accept state → accept.
  • Otherwise → reject.

Example DFA — Strings ending with "ab"

Alphabet: Σ = {a, b} States:

• q0: haven’t seen "a" yet.
• q1: just saw "a".
• q2: just saw "ab" → accept state.

Transitions:

• From q0:
  • on a → go to q1
  • on b → stay at q0
• From q1:
  • on a → stay at q1
  • on b → go to q2
• From q2:
  • on a → go to q1
  • on b → stay at q0

Accept state: q2. So:

• "aab" → q0 → q1 → q1 → q2 → ✅ accept.
• "abb" → q0 → q1 → q2 → q0 → ❌ reject.

NFA

The difference is in the transition function δ:

• In DFA: δ(q, a) → exactly one state.
• In NFA: δ(q, a) → zero, one, or many states.

Also:

• NFAs allow ε-moves (transitions without consuming input).

This means:

• At each step, the machine may “branch” into multiple possible futures.”
• If any one branch leads to an accept state when input ends → the NFA accepts.