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.