Deterministic finite automata: trace one state at a time

After reading 01, the example machine is in a “yes” state. It must still process another symbol when one is present. That final check is easy to overlook: stopping at the first match would build a machine for “contains 01”, not “ends in 01”.

Choose the three things to remember#

A state is the information the machine keeps between input symbols. For this illustrative checker, three states suffice:

State	What it remembers
q0	No useful ending has been seen; also the starting state.
q1	The latest symbol is 0.
q2	The latest two symbols are 01.

Only q2 is accepting. The allowed input symbols, collectively called the alphabet, are 0 and 1. For every state and symbol, the transition table names the next state:

Current state	Read 0	Read 1
q0	q1	q0
q1	q1	q2
q2	q1	q0

In q2, another 0 begins a possible new match, so move to q1. Another 1 leaves no useful ending, so move to q0. These transitions explain why reaching an accepting state does not stop the input.

Predict whether 010 should be accepted before trying it. Enter 010, choose Load input, then choose Read next symbol twice. The machine has read 01 and reached q2, but the final 0 is still unread. It is in an accepting state without having finished the input.

Try the worked example

Load a binary string, then read one symbol at a time. Reset trace restores the last loaded input and starts it again.

Binary input (32 symbols max) Load input Read next symbol Reset trace

This illustrative machine checks whether a binary string ends in 01. The demo allows up to 32 symbols; it does not edit the transition rules.

Loaded input: 1101. Read 0 of 4 symbols.

Consumed: none (empty string). Remaining: 1101.

Current state: q0. Last transition: none yet.

Input remains. Read the next symbol before deciding acceptance.

Worked examples

1101: q0 → q0 → q0 → q1 → q2. All four symbols have been read, so the input is accepted.

010: q0 → q1 → q2 → q1. After 01, the machine reaches q2, but 0 remains. Reading that final symbol moves to q1, so the complete input is rejected.

Read the final 0: the transition q2 → q1 exhausts 010, so the complete input is rejected. Reset trace rewinds the loaded string to q0. Editing the field prepares a new input; choose Load input to start its trace. Try 102 too: 2 at position 3 is outside the alphabet, making the input invalid rather than a rejected binary string.

Keep reading after an early match#

For 1101, begin at q0. The two leading 1 symbols keep the state at q0; 0 moves to q1; the final 1 moves to q2. The exhausted input is accepted.

For 010, the states are q0 → q1 → q2 → q1. The machine visited the accepting state but did not finish there. It rejects this input.

This Python example encodes exactly that table. It treats characters outside the chosen alphabet as invalid input rather than silently assigning them transitions.

def ends_in_01(bits: str) -> bool:
    transitions = {
        "q0": {"0": "q1", "1": "q0"},
        "q1": {"0": "q1", "1": "q2"},
        "q2": {"0": "q1", "1": "q0"},
    }
    state = "q0"
    for bit in bits:
        if bit not in ("0", "1"):
            raise ValueError("input must contain only 0 and 1")
        state = transitions[state][bit]
    return state == "q2"

The function takes one transition for each input symbol. Its remembered state does not grow with the input length. The example is a teaching implementation; a direct string operation would be simpler for this one fixed suffix check.

What the machine can and cannot remember#

Deterministic means that one current state and one allowed symbol select exactly one next state. It says nothing about whether the next symbol is predictable. A nondeterministic finite automaton, or NFA, may allow several next states; it can still be converted into a DFA recognising the same regular language.

The finite set of states is also a limit. A fixed-size DFA cannot remember an arbitrarily deep stack of opening brackets and check that every one is later closed. Restricting the maximum nesting depth would be a different, bounded problem.

A compiler’s scanner can use a state machine to recognise a token’s shape, but recognising tokens is not the same as parsing arbitrary nested program structure. The compiler versus interpreter guide puts those jobs in context. The Luhn algorithm shows another validation rule, this time stated as arithmetic over digits. The UC Davis automata simulator documentation describes stepping through DFA and NFA execution.

When designing a state machine, ask what information from the past can change the final answer. Give each state that specific meaning, then test an input that reaches “yes” early but should finish at “no”.

Questions people also ask

2 QUESTIONS

▸ Can there be two possible next states for the same symbol?

Not in a DFA: the current state and allowed input symbol specify exactly one next state. An NFA can have several possible next states; both models recognise regular languages.

▸ What happens on an empty input?

The machine stays in its start state. It accepts an empty string only when that start state is accepting. In the ending-in-01 example it is not, so the empty string is rejected.