Course contentsShow
← Computer Science
Lesson 1783 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

DFA Transition Tables

Representing DFAs using transition tables as an alternative to state diagrams for formal specifications.

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.