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

Combining Conditions with Product Construction

Building DFAs that recognize the intersection of two languages by creating states as ordered pairs.

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

  1. States: If DFA₁ has 3 states and DFA₂ has 2 states, the product DFA has 3 × 2 = 6 states (all possible pairs).

  2. Start state: The pair of both start states: (q₀₁, q₀₂).

  3. Transitions: From state (q₁, q₂) on input symbol a, move to (δ₁(q₁, a), δ₂(q₂, a))—apply both transition functions.

  4. Accept states: A pair (q₁, q₂) is accepting if both q₁ and q₂ 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.