Running a DFA

A DFA is five things: a set of states, an alphabet, a transition function, one start state, and a set of accepting states. The word deterministic is a claim about the transition function alone — from every state, for every symbol, there is exactly one arrow out. Not zero, not two.

That single restriction is what makes a DFA implementable as a while loop over a lookup table. There is never anything to decide, so there is never anything to backtrack over, and the machine reads each character exactly once.

A DFA's memory is its current state and nothing else. With three states it can distinguish exactly three situations — no more, no matter how long the input.

Alphabet (Σ)

The finite set of symbols the machine may read. For everything on this page, Σ = {a, b}.

String and language

A string is a finite sequence of symbols from Σ. A language is a set of strings — usually infinite. A machine does not compute a value; it answers one yes/no question about membership in a language.

State

The machine's entire memory. Not part of it — all of it. If two different inputs leave the machine in the same state, it can never again tell them apart.

Transition function (δ)

Where to go given the current state and the next symbol. For a DFA it is a function: exactly one answer, always. For an NFA it returns a set, possibly empty.

Accepting state

Drawn as a double circle. A string is accepted if the machine is in one of these when the input runs out — not if it merely passed through one on the way.

Trap or dead state

A non-accepting state with every symbol looping back to itself. Once you fall in you can never get out, so the answer is already no. Diagrams usually omit it and leave the arrow missing instead.

The DFA below accepts exactly the strings over {a, b} that end in `ab`. Three states are enough, and each one has a job you can say in a sentence:

Read the table as a claim about suffixes. The machine never stores the string — it stores only the answer to "how much of ab have I just seen?", which has exactly three possible answers. That is why three states suffice for a language with infinitely many strings in it.

1. 1Start in q0 with the whole string unread.
2. 2Read the next symbol and follow the one arrow that matches it.
3. 3Repeat until the input is exhausted.
4. 4Accept if and only if the state you stopped in is a double circle.

Two arrows in this machine point back at the state they left: q0 on b, and q1 on a. Beginners tend to leave these out, and the machine then silently rejects most of its language.

• q0 --b--> q0 says a b at the start gets you no closer to ab, but it does not disqualify anything either.
• q1 --a--> q1 says aa is no worse than a — you have still just seen an a, so you are still one b from accepting.
• q2 --a--> q1 is the interesting one: having matched ab, reading another a loses the match. Acceptance is about where you finish, so passing through q2 earns nothing.

The classic non-example is aⁿbⁿ — equal numbers of as then bs. No DFA recognises it, and the reason is exactly the finiteness of the state set: to check the count you would need a distinct state for every possible number of as, and there are infinitely many. This is what the pumping lemma formalises.