Deterministic Finite Automata: Definition and Design

A deterministic finite automaton (DFA) is the simplest model of computation the simulator supports: a machine with a fixed, finite set of states and exactly one move available for every state/symbol pair. There is never a choice to make, which is what "deterministic" means here.

The formal definition

A DFA is a 5-tuple M = (Q, Σ, δ, q₀, F):

• Q: a finite set of states.
• Σ: a finite input alphabet.
• δ: Q × Σ → Q: the transition function. For every state and every symbol, δ names exactly one next state.
• q₀ ∈ Q: the start state.
• F ⊆ Q: the set of accept states.

Running the machine on an input string means starting at q₀ and repeatedly applying δ, one input symbol at a time, until the string is exhausted. The string is accepted if the machine ends in a state in F, rejected otherwise.

Designing a DFA: strings ending in "01"

Suppose the language is every binary string that ends in 01. Design starts by asking: what does the machine need to remember about the input seen so far? Here, just enough of the suffix to know whether the last two symbols read were 0 then 1. That gives three states:

• q0 (start): the last symbol read, if any, was not part of a "0 then 1" in progress.
• q1: the last symbol read was 0 — a candidate start of the suffix.
• q2 (accept): the last two symbols read were exactly 01.

From there the transitions fall out mechanically: on a 0, always move to (or stay at) q1, since the string now ends in a fresh 0. On a 1, move to q2 only if the state was q1 (meaning the two most recent symbols are now 0, 1); otherwise fall back to q0.

q0⊢q1⊢q1⊢q2⊢∈ F

Click a transition arrow to see the symbol it consumes, or type a string into the test panel — every prefix traces a path through exactly one state at a time, which is the deterministic part in action.

Your turn