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

DFAs for Union of Languages

Using product construction with modified accept states to build a DFA recognizing the union of two languages.

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₂:

  1. States: Create pairs (q₁, q₂) representing being in state q₁ of M₁ and q₂ of M₂
  2. Transitions: From (q₁, q₂) on symbol a, go to (δ₁(q₁, a), δ₂(q₂, a))—advance both machines
  3. Start state: (s₁, s₂) where s₁ and s₂ are the start states
  4. 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.