2.1 DFA Design and Execution: Making Every State Meaningful

This lesson designs a deterministic finite automaton that recognizes strings ending in abb, and transforms the state diagram into an executable transition table.

Learning Objectives

• Write the five-tuple definition of a DFA;
• Construct a DFA using state invariants rather than guessing transitions;
• Understand rejection states and the complete transition function;
• Test state meanings and transition boundaries.

1. The Five Components of a DFA

A deterministic finite automaton is written as:

$$M=(Q,\mathrm{\Sigma },\delta ,q_0,F).$$

• $Q$: a finite set of states;
• $\mathrm{\Sigma }$: the input alphabet;
• $\delta :Q\times \mathrm{\Sigma }\to Q$: the transition function;
• $q_0\in Q$: the initial state;
• $F\subseteq Q$: the set of accepting states.

A DFA satisfies two requirements: for any given state and input symbol, there is exactly one next state; there are no ε-transitions that move without reading an input symbol. In the formal definition, $\delta$ is a total function, every state must have a defined transition for every symbol in the alphabet. Edges omitted from diagrams typically imply a transition to a rejecting or trap state.

2. Extending Transition: Processing the Entire String

A single-step transition reads only one symbol. The extended transition function ${\delta }^{\ast }$ is recursively defined as:

$${\delta }^{\ast }(q,\epsilon )=q,$$$${\delta }^{\ast }(q,wa)=\delta ({\delta }^{\ast }(q,w),a).$$

A DFA accepts a string $w$ if and only if:

$${\delta }^{\ast }(q_0,w)\in F.$$

The automaton does not accept simply because it has previously passed through an accepting state; it must check the final state after processing the entire input. The longest-match strategy in lexical analysis may additionally record the last position where an accepting state was reached, this is scanner policy, not part of the DFA's formal definition.

3. Write the State Invariants First

For the language

$$L=\{w\in \{a,b{\}}^{\ast }\mid w\text{ ends with }abb\},$$

the state only needs to track how much of the target abb's prefix matches the current input suffix.

State	Invariant satisfied by the read prefix
q0	The longest overlap between the current suffix and an abb prefix has length 0
q1	The current input ends with a
q2	The current input ends with ab
q3	The current input ends with abb, and this is an accepting state

This yields the complete transition table:

Current State	Read a	Read b
q0	q1	q0
q1	q1	q2
q2	q1	q3
q3	q1	q0

q3 continues matching upon receiving a new character. It is not a terminal state; for example, abba does not end with abb, so it must transition from q3 to q1 and ultimately reject.

4. Implementing the Transition Table

This Python 3.9+ example accepts a finite string or sequence of symbols. Save and run it; successful assertions produce no output:

from collections.abc import Iterable

TRANSITIONS = {
    "q0": {"a": "q1", "b": "q0"},
    "q1": {"a": "q1", "b": "q2"},
    "q2": {"a": "q1", "b": "q3"},
    "q3": {"a": "q1", "b": "q0"},
}
ACCEPTING = {"q3"}

def accepts_ending_abb(symbols: Iterable[str]) -> bool:
    state = "q0"
    for symbol in symbols:
        if symbol not in {"a", "b"}:
            raise ValueError(f"Alphabet does not contain {symbol!r}")
        state = TRANSITIONS[state][symbol]
    return state in ACCEPTING

cases = {
    "": False,
    "abb": True,
    "aabb": True,
    "ababb": True,
    "abba": False,
    "bbb": False,
}
for text, expected in cases.items():
    assert accepts_ending_abb(text) is expected

Input such as abc raises ValueError. A missing entry in the transition table should instead expose a configuration error, not masquerade as invalid user input. An input of length $n$ over the alphabet performs $n$ transitions, resulting in a time complexity of $O(n)$ and an additional state space of $O(1)$. If the requirement is to verify that no character at any position violates the rules, the worst-case scenario necessitates examining the entire input. However, a specific implementation might fail early upon encountering an invalid character.

5. Two Common State Construction Methods

Split States by What Has Been Learned

For example, to recognize strings that contain both a and b, the state can represent two boolean facts: whether a has been seen, and whether b has been seen. There are four possible combinations of these facts, resulting in exactly four distinct states.

Merge States Based on Identical Future Responses

If two historical prefixes respond identically to any subsequent input (accepting or rejecting in the same way) they do not need to be separate states. This idea is formally defined by the Myhill–Nerode relation and forms the theoretical foundation for minimizing deterministic finite automata (DFA).

6. When Trap States Need to Be Explicitly Defined

When identifying an identifier, if the first character is a digit, no subsequent character can make the entire string valid. A trap state can be entered:

start --letter/_--> identifier
start --digit/other--> dead
identifier --letter/digit/_--> identifier
identifier --other--> dead
dead --any--> dead

If the scanner operates on tokens, "other characters" might indicate the end of the current token rather than a fully invalid input. Therefore, the same state diagram cannot be interpreted without reference to the input protocol: are we validating the entire string, or are we extracting the longest possible token from the character stream?

7. Test Coverage of State Significance

Don't just list a few "seemingly normal" strings. For each state, design:

• The shortest input that can reach that state;
• The input that transitions from that state to an accepting state;
• An input that differs by a single character and should be rejected;
• The empty string and characters outside the alphabet;
• The scenario where input continues after acceptance.

State invariants can also serve as test assertions: after processing any prefix, the current state must match the longest suffix that is also a prefix of abb, including the whole target when it matches.

Common Misconceptions

• No outgoing edges from an accepting state: A DFA must continue processing the remaining input. Accepting states do not terminate the computation.
• Missing edges mean staying in place: Such edges typically represent omitted failure transitions; their semantics must be explicitly defined and unambiguous.
• State names are inherently part of the design: The label q7 does not explain a state. Write its invariant first; neatly numbered states can still take the wrong turn.
• DFA can only recognize fixed strings: Finite state machines can express infinite regular languages, such as recognizing an even number of 1 symbols in strings of any finite length.

Exercise

1. Design a DFA that recognizes strings containing the substring abb, and compare the outgoing edges from the accepting states with those that match the pattern ending in abb.
2. Design a DFA that recognizes binary numbers whose value modulo 3 is zero, and explain the meaning of the remainder in each state.
3. Complete the trap state and test cases for the ASCII identifier recognizer.
4. Add a function to the code from this lesson that returns both the final state and the full state transition path.

Summary

The core of a DFA is not circles and arrows, but a finite, verifiable summary of history. State invariants describe what is already known, while the complete transition table specifies how each new symbol updates that summary.

The next lesson allows a machine to retain multiple possible states simultaneously. It does not expand the range of regular languages, yet it makes the construction of "choices" and "optional paths" significantly simpler.