Combining Conditions with Product Construction
What you'll learn: How to build a DFA that recognizes the intersection of two languages by pairing up states from both machines.
The Core Idea
Imagine you have two DFAs: one that accepts strings ending in "0" and another that accepts strings with an even number of "1"s. What if you need a single DFA that accepts strings satisfying both conditions?
Product construction solves this by creating a new DFA whose states are ordered pairs (q₁, q₂), where q₁ is a state from the first DFA and q₂ is a state from the second. The new machine simulates running both DFAs simultaneously—like tracking two conditions at once.
How It Works
-
States: If DFA₁ has 3 states and DFA₂ has 2 states, the product DFA has 3 × 2 = 6 states (all possible pairs).
-
Start state: The pair of both start states:
(q₀₁, q₀₂). -
Transitions: From state
(q₁, q₂)on input symbola, move to(δ₁(q₁, a), δ₂(q₂, a))—apply both transition functions. -
Accept states: A pair
(q₁, q₂)is accepting if bothq₁andq₂are accepting states in their respective DFAs.
Example in Plain English
- DFA₁ state: "Have I seen an even number of 0s?"
- DFA₂ state: "Does the string start with 1?"
- Product state
(even0s, startsWith1)tracks both questions at every step.
The intersection language is recognized by accepting only when both conditions hold.
Key Takeaway: Product construction builds a DFA for L₁ ∩ L₂ by creating states as ordered pairs and accepting when both component states accept—effectively running two machines in parallel.