Machines and Recognition

A language is usually infinite, so it cannot be listed. What can exist is a finite object that settles membership for any string you hand it. That object is a machine, and the trade — finite description, infinite question — is the reason the subject exists.

Q — a finite set of states

A state is a summary of everything seen so far that could still matter. For "an even number of a's", the only thing worth remembering is even-or-odd, which is why two states suffice. Finite is the crucial word: it is the machine's entire memory.

Σ — the input alphabet

What the machine is allowed to read, one symbol per step.

δ — the transition function

δ : Q × Σ → Q. Where to go, given where you are and what you just read. This is the only part that changes between the machine models in this course.

q₀ — the start state

Exactly one, always. Every run begins here with nothing read, which is what makes a machine's behaviour on a string a fixed fact rather than a choice.

F ⊆ Q — the accepting states

A subset you choose. F may be empty (accepting nothing) or all of Q (accepting everything). Swapping F for Q − F in a DFA gives you a machine for the complement language, which is a one-line proof worth remembering.

Written together: M = (Q, Σ, δ, q₀, F). An NFA changes only δ, to return a set. A PDA adds a stack to δ's inputs and outputs. A Turing machine lets δ write and move. Everything later is a variation on δ.

δ is a function, so for every (state, symbol) pair there is exactly one answer: never zero, never two. Two states and two symbols means four pairs, so a complete DFA has exactly four transitions.

This is why a DFA's run on a string is unique. There is nothing to search, nothing to backtrack over, and the machine's answer does not depend on any choice. It also means a DFA needs a transition for every symbol in every state, including the ones that lead nowhere useful — which is what a dead or trap state is for.

A configuration is the machine's complete situation: the current state, and the input not yet read. That is all — there is no history, no counter, no copy of what was already consumed.

1. 1Start in q₀ with the whole string ahead of you.
2. 2Read one symbol, follow the single transition δ says to follow, and discard the symbol.
3. 3Repeat until the input is exhausted. A string of length n always takes exactly n transitions, self-loops included.
4. 4Now — and only now — check whether the state you are standing in is in F. If it is, accept; otherwise reject.

Passing through an accepting state part-way through means nothing whatsoever. Acceptance is decided once, when the input runs out.

L(M) — the language of M — is the set of every string M accepts. M recognises L when L(M) = L, which is a two-way claim: every string in L is accepted, and every string not in L is rejected. Getting one direction right is only half a proof.

Two machines with L(M₁) = L(M₂) are equivalent, however differently they are drawn. That is what makes minimisation meaningful — and what makes it possible to convert an NFA to a DFA and still be talking about the same language.

The machine's entire memory is which state it is in, and there are finitely many states. So if a language requires distinguishing unboundedly many different situations, no finite automaton can recognise it.

{ aⁿbⁿ : n ≥ 0 } is the standard example. To match the b's you must know how many a's you saw, and n is unbounded, so two different counts must eventually land in the same state — after which the machine can never tell them apart again. That collision is exactly what the pumping lemma formalises, and adding a stack or a tape is the only escape.