All primers · Computer science

Finite automata in 10 minutes

How a deterministic finite automaton reads a string, and how to trace one from a transition table without paper.

The idea

A deterministic finite automaton (DFA) is a machine with a fixed set of states. It reads a string one symbol at a time. For each state and each symbol, a transition table says which state comes next. One state is the start state; some are accepting states.

After the last symbol, the string is accepted if the machine is in an accepting state. The machine has no other memory: everything it knows about the symbols so far is encoded in its current state.

How to trace one quickly

Write nothing down: keep only the current state in your head. Read the next symbol, look up the row for your state, move, repeat. Count symbols on your fingers if the string is long.

Look for what each state means. In many passages, states stand for something simple, such as "the last symbol was a" or "the number of b's so far is even". Once you name the states, questions like "which strings are accepted?" become easy.

Typical question patterns

Which of four strings is accepted? Which state does the machine end in? What is the shortest accepted string? Which description matches all accepted strings (for example, "ends in ab")?

Check yourself

  1. A DFA has states S0 (start) and S1 (accepting). On a it always goes to S1, on b it always goes to S0. Is "abba" accepted?

    Show answer

    Yes. Only the last symbol matters: the last symbol is a, so the machine ends in S1.

  2. Can a DFA remember how many symbols it has read, for any length?

    Show answer

    No. It has finitely many states, so it can only remember finitely many situations, such as "even or odd".

Practise General Academic passages →