DFAs for Union of Languages
You'll learn how to construct a DFA that accepts strings belonging to either of two languages by modifying the product construction's accept conditions.
The Core Idea
Remember from the previous lesson that product construction lets you run two DFAs "in parallel" by creating states that track where both machines would be simultaneously. For union, we want to accept if either original DFA would accept—not both like with intersection.
The construction is almost identical to what you've seen before, but with one critical difference in the final step.
Building a Union DFA
Given two DFAs M₁ and M₂:
- States: Create pairs
(q₁, q₂)representing being in stateq₁of M₁ andq₂of M₂ - Transitions: From
(q₁, q₂)on symbola, go to(δ₁(q₁, a), δ₂(q₂, a))—advance both machines - Start state:
(s₁, s₂)wheres₁ands₂are the start states - Accept states: Here's the key difference! Mark
(q₁, q₂)as accepting if q₁ is accepting OR q₂ is accepting (or both)
Intuition
Think of it like two bouncers at a club entrance. With union, you get in if either bouncer approves you. With intersection (previous lesson), you needed both to approve. Same parallel simulation, different voting rule.
If M₁ accepts language L₁ and M₂ accepts L₂, this construction gives you a DFA accepting L₁ ∪ L₂.
Example
If L₁ = strings ending in "0" and L₂ = strings with even length, then L₁ ∪ L₂ accepts strings that end in "0" or have even length (or both). The union DFA accepts "0", "10", "aa", "101"—anything satisfying either condition.
Key Takeaway: Product construction with OR-based accept states builds a DFA for the union of two languages, accepting when at least one component DFA would accept.