Notebook 5: Product Automaton — Intersection of DFAs

Interactive notebook on the product automaton construction for computing the intersection of two DFAs. Visualizes the cross-product state space step by step, from the VVT course at UniUD.

Product Automaton (DFA Intersection)

This notebook walks through the product automaton construction that builds a DFA recognising \(L(A_1) \cap L(A_2)\) from two given DFAs. The running example uses two automata over \(\Sigma = \{a,b\}\):

\(A_1\) — “ends in \(a\)”:

  • States: \(p_0\) (initial, non-accepting), \(p_1\) (accepting)
  • \(\delta_1(p_0,a)=p_1\), \(\delta_1(p_0,b)=p_0\), \(\delta_1(p_1,a)=p_1\), \(\delta_1(p_1,b)=p_0\)

\(A_2\) — “even number of \(a\)’s”:

  • States: \(r_0\) (initial, accepting), \(r_1\) (non-accepting)
  • \(\delta_2(r_0,a)=r_1\), \(\delta_2(r_0,b)=r_0\), \(\delta_2(r_1,a)=r_0\), \(\delta_2(r_1,b)=r_1\)

Product automaton: 4 states \(\{(p_0,r_0),\,(p_0,r_1),\,(p_1,r_0),\,(p_1,r_1)\}\), with accepting set \(F = F_1 \times F_2 = \{(p_1,r_0)\}\).

Widget 1: Step-by-Step Product Construction

Click Step → to advance through the product construction one micro-step at a time.

Step 0 / 14
WORKLIST
PROCESSED

A₁ — ends in a

b a b a p₀ p₁

A₂ — even # of a's

b a a b r₀ r₁

Product Automaton

Product Transition Table

State a b

Widget 2: Word Simulation

Type a word over \(\{a,b\}\) (default aab) and step through it on all three automata simultaneously: \(A_1\), \(A_2\), and the product. The invariant: the product state always equals \((A_1\text{ state},\, A_2\text{ state})\).

A₁ — ends in a

b a b a p₀ p₁

A₂ — even # of a's

b a a b r₀ r₁

Product — A₁ ∩ A₂

b a b a a b a b (p₀,r₀) (p₀,r₁) (p₁,r₀) (p₁,r₁)

Simulation Trace

Prefix A₁ state A₂ state Product state A₁ acc? A₂ acc? Product acc?

What To Notice

  1. The product state is always the pair of component states — no information is lost or added. At every moment in Widget 2 the product state equals \((\text{A}_1\text{ state},\,\text{A}_2\text{ state})\). The product construction simply runs both automata in lock-step and packages the two states into one.

  2. Only \((p_1,r_0)\) is accepting: the word must end in \(a\) AND have an even count of \(a\)’s. Acceptance in the product requires membership in \(F_1 \times F_2\), i.e.
    the current state must be accepting in both components simultaneously.

  3. The word “a” reaches \((p_1,r_1)\) — ends in \(a\) but odd count — rejected. One condition is met (\(A_1\) accepts) but the other fails (\(A_2\) rejects), so the product rejects. Try it in Widget 2.

  4. The word “aa” reaches \((p_1,r_0)\) — accepted by both conditions. Two \(a\)’s give an even count and the word ends in \(a\). This is the simplest accepted word.