DFA Transition Tables
You'll learn how to represent a DFA using a table format instead of a state diagram, making it easier to write down and process formally.
While state diagrams are visually intuitive, they can become cluttered with many states and transitions. A transition table provides an alternative, tabular representation of exactly the same information. Think of it as switching from a map with arrows to a written set of directions—both get you to the same destination, just presented differently.
Structure of a Transition Table
A DFA transition table is organized as follows:
- Rows represent each state in the DFA
- Columns represent each symbol in the alphabet
- Cells contain the destination state when reading that symbol from that state
- The start state is typically marked (often with an arrow →)
- Accept states are typically marked (often with an asterisk *)
Example
Consider a DFA over alphabet {0, 1} that accepts strings ending in "01":
| 0 | 1 |
------|----|----|
→ q0 | q1 | q0 |
q1 | q1 | q2*|
* q2 | q1 | q0 |
This table says: "From state q0, reading 0 takes you to q1; reading 1 keeps you in q0." Each row captures all outgoing transitions from that state.
When to Use Tables vs Diagrams
Transition tables excel when:
- Implementing DFAs in code (tables map directly to 2D arrays or dictionaries)
- Documenting DFAs formally in papers or specifications
- Working with many states where diagrams become messy
State diagrams remain better for visual understanding and initial design.
Key Takeaway: A DFA transition table is a matrix representation of state transitions—same automaton as a diagram, but formatted as rows (states) × columns (input symbols), making it more suitable for formal specification and implementation.