Automata & Formal Languages · Instrument 01 · Finite Automata

Recognizing with finite memory

A finite automaton is a fixed set of states wired together by transitions — the leanest model of computation. Run a string through it, watch it land in an accepting state or not. Then meet nondeterminism, the powerset trick that tames it, and the algorithm that finds the smallest machine for a language.

DFA

NFA

Subset construction

Minimization

Divisible by 3 (binary)

number n21

State = remainder of the number-so-far mod 3. Reading bit b doubles and adds: r → (2r+b) mod 3. The start state (remainder 0) is also the only accepting one, so the machine accepts exactly the multiples of 3 — with just three states.

DFA

Nondeterministic automaton

Build a string

The machine is in a set of states at once. Each symbol maps every active state to its successors; an ε-edge is taken for free, so the active set is closed under ε first. It accepts if any active state is accepting — one accepting path is enough.

NFA

NFA → DFA (powerset)

Each DFA state is a set of NFA states the machine could be in. Start from the ε-closure of the start state; for each symbol, take the union of successors and close — that's a new DFA state. A DFA state accepts if its set contains any NFA accepting state.

subset construction

Partition refinement

Start by splitting states into accepting and non-accepting. Refine: two states stay together only if, for every symbol, they move to the same group. Repeat until stable — each surviving group becomes one state of the unique smallest DFA.

DFA minimization