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

DFA Definition and Components

Understanding the five-tuple definition of a DFA: states, alphabet, transition function, start state, and accept states.

DFA Definition and Components

What you'll learn: You'll understand exactly what makes up a Deterministic Finite Automaton (DFA) by examining its five formal components.

The Five-Tuple Definition

A Deterministic Finite Automaton (DFA) is a mathematical model of computation defined as a 5-tuple: (Q, Σ, δ, q₀, F). Think of it as a simple machine with exactly five building blocks that work together to recognize patterns in strings.

The Five Components

1. Q: The Set of States

A finite collection of possible "positions" or "modes" the machine can be in. Like rooms in a house—the machine is always in exactly one room at a time.

2. Σ: The Alphabet

The finite set of input symbols the DFA can read. This is the same alphabet concept you learned earlier—for example, {0, 1} for binary strings.

3. δ: The Transition Function

A function δ: Q × Σ → Q that tells the machine: "If you're in state q and read symbol a, move to state r." It's deterministic—every combination has exactly one outcome, like a rulebook with no ambiguity.

4. q₀: The Start State

The designated state in Q where the DFA begins processing. Every machine needs a starting point.

5. F: The Accept States

A subset of Q representing "good" or "accepting" final states. If the DFA finishes reading input while in one of these states, it accepts the string.

How They Work Together

When you feed a string to a DFA, it starts at q₀, reads symbols one by one, follows δ to move between states in Q, and accepts if it ends in a state from F.

Key Takeaway: A DFA is formally defined by five components—states (Q), alphabet (Σ), transition function (δ), start state (q₀), and accept states (F)—which together create a precise machine for recognizing languages.