The simplest computational model — and the foundation of everything
Use Arrow Keys to navigate • Interactive Canvas visualizations throughout
Where DFAs fit in the Chomsky hierarchy
The simplest class in the hierarchy. Every DFA reads input left-to-right, one symbol at a time, with no memory beyond its current state.
A DFA is like a vending machine with a fixed set of buttons. It has no scratch paper, no stack, no tape — just a finite number of states and transitions between them.
Click on the hierarchy levels to highlight them.
A DFA is just a machine that reads input and changes state
A turnstile has two states: Locked and Unlocked. Insert a coin → unlocks. Push → locks again. This IS a DFA!
A DFA is defined as M = (Q, Σ, δ, q₀, F)
Every state must have exactly one transition for every symbol. If you can't think of where to go, add a dead state (trap state) that rejects.
Hover over the DFA diagram to see each component highlighted.
Processing an entire string, one symbol at a time
Base: δ̂(q, ε) = q
Inductive: δ̂(q, wa) = δ(δ̂(q, w), a)
In plain English: process all of w first to get some state, then take one more step on symbol a.
The classic first DFA — accepts binary strings with an even count of 0s
The DFA only needs to remember one bit of information: is the count of 0s seen so far even or odd?
| State | 0 | 1 |
|---|---|---|
| → *E | O | E |
| O | E | O |
→ = start, * = accept. On 1, state unchanged (1 doesn't affect 0-count). On 0, state toggles.
Enter any binary string — watch the "even 0s" DFA process it live
The DFA acts as a parity checker. Each 0 toggles between E and O. Each 1 stays put. After reading all input, if we're at E, the count was even.
L(A) = the set of all strings the DFA accepts
L(A) = { w ∈ Σ* | δ̂(q₀, w) ∈ F }
The language is all strings w such that, starting from q₀ and reading all of w, you end up in an accept state.
L(A) = { w ∈ {0,1}* | w has an even number of 0s }
A language is regular if and only if some DFA recognizes it. The class of regular languages equals the class of DFA-recognizable languages.
A systematic approach to building DFAs from scratch
Ask yourself: "What do I need to remember about the input so far?" Each distinct "memory situation" becomes a state.
What do I need to remember? The last 1-2 characters.
Don't try to remember the entire input. DFAs have finite memory. Focus on what matters for the acceptance condition.
Watch the DFA get constructed step by step
q₀: no useful suffix yet
q₁: last char was 0
q₂: last two chars were 01 (accept)
Combining two DFAs to handle union and intersection
Given DFA₁ = (Q₁, Σ, δ₁, q₁, F₁) and DFA₂ = (Q₂, Σ, δ₂, q₂, F₂):
Imagine running both DFAs simultaneously on the same input. Each state in the product tracks where both DFAs are. For union, accept if either accepts. For intersection, accept if both accept.
Given this DFA, predict whether each string is accepted or rejected
DFA accepts strings over {a,b} that contain "ab" as a substring.
1. Input: "ba"
2. Input: "aab"
3. Input: "bbb"
4. Input: "abba"
To complement, just swap accept and non-accept states
Given DFA A = (Q, Σ, δ, q₀, F):
Complement: A' = (Q, Σ, δ, q₀, Q \ F)
Same states, same transitions, same start. Just flip which states are accepting!
You cannot complement an NFA by swapping accept states. You must first convert to a DFA, then complement. This is a classic exam mistake.
Since δ is a total function, every string ends in exactly one state. If that state was accepting, it's now rejecting, and vice versa. Every string changes sides.
Model a tennis game as a DFA — who wins?
Score: Love-Love
State: 0-0
Σ = {s, o} — server or opponent wins a point
States = all possible score combinations
Accept = "Server Wins"
Note the deuce rule: at 40-40, someone must win by 2 points.
This DFA is supposed to accept strings with an even number of 1s, but it has a bug
Find equivalent states and merge them to get the smallest DFA
The theoretical foundation for DFA minimization
A language L is regular if and only if the relation ≡L has a finite number of equivalence classes.
Moreover: the number of classes = the number of states in the minimum DFA.
x ≡L y iff for ALL strings z: xz ∈ L ↔ yz ∈ L
Two strings are equivalent if no suffix z can tell them apart.
Strings "10" and "0" are NOT equivalent: with z="0", "100" has 1 zero (reject) but "00" has 2 zeros (accept).
But "10" and "110" ARE equivalent: both have exactly 1 zero, so same parity for any suffix.
Common patterns you'll use again and again
Two states: "not yet seen a" and "seen a". Once you see an 'a', stay in accept forever.
States needed: 2
The number of states reflects how much you need to remember. "At least one" needs 1 bit. "Ends with xy" needs to track the last 2 chars. "Divisibility by n" needs n remainder states.
For each language, choose the correct number of states needed
1. L = { w ∈ {0,1}* | w has at least three 1s }
2. L = { w ∈ {a,b}* | w ends with "aba" }
3. L = { w ∈ {0,1}* | binary value of w is divisible by 5 }
4. To complement a DFA, you need to:
Pitfalls that cost points on exams
Every state must have exactly one transition per symbol. If you forget one, it's not a valid DFA. Add a dead/trap state for unwanted transitions.
When a path should reject, don't just "leave it hanging." Add a non-accepting state with self-loops on all symbols.
You cannot swap accept states on an NFA to get the complement. You must first convert NFA → DFA, THEN complement. This is because NFAs can be in multiple states simultaneously.
Having more states doesn't mean the language is "harder." The minimum DFA state count is determined by the Myhill-Nerode equivalence classes.
When defining a DFA formally, you must specify ALL five components: Q, Σ, δ, q₀, F. Missing any one makes the definition invalid.
Everything you need to know on one slide
Test your understanding of DFA fundamentals
Q1: What makes a DFA "deterministic"?
Q2: What is the minimum # of states for a DFA accepting {w | w has odd # of a's}?
Q3: In the product construction for L₁ ∩ L₂, a state (p,q) is accepting when:
Given this DFA, trace the input and determine the result
DFA: divisible by 3 in binary. States = remainders {0, 1, 2}. Accept = {0}.
Fill in each state transition:
Build the transition table for a DFA that accepts strings over {a,b} with an even number of a's AND an even number of b's
You need to track the parity of BOTH a's and b's. Think product construction: one DFA for even a's × one DFA for even b's.
States: (even-a, even-b), (even-a, odd-b), (odd-a, even-b), (odd-a, odd-b)
Shorthand: EE, EO, OE, OO
Start state: EE (0 a's and 0 b's — both even)
Accept state: EE
| State | on 'a' | on 'b' |
|---|---|---|
| EE (start, accept) | ||
| EO | ||
| OE | ||
| OO |