Constructing and Proving Product DFAs for Boolean Language Combinations

Hello, and welcome to Theory of Computation. This opening module develops the proof techniques behind regular languages: not merely drawing automata, but constructing them systematically and proving that they recognize exactly the intended languages.

This lesson introduces the product DFA, the central construction behind closure under Boolean operations. Given DFAs for two languages, you will build one DFA that tracks both computations on the same input. By choosing its accepting states appropriately, the same construction handles intersection, union, difference, symmetric difference, and any other Boolean combination.

If DFA notation is new or needs refreshing, begin with this short formal review.

---

One machine that remembers two computations

Let

$$M_1=(Q_1,\Sigma ,{\delta }_1,s_1,F_1)$$

and

$$M_2=(Q_2,\Sigma ,{\delta }_2,s_2,F_2)$$

be DFAs recognizing languages $L_1$ and $L_2$, respectively.

The important condition is that both machines operate over the same alphabet $\Sigma$. If two language descriptions begin with different alphabets, choose a common alphabet—usually their union—and ensure that each DFA has a transition on every symbol in it. A missing transition can be supplied by a nonaccepting sink state. This matters because a DFA’s transition function must be total.

A product DFA simulates $M_1$ and $M_2$ in parallel. Its state is a pair:

$$(p,q)$$

where $p$ says where $M_1$ would be after reading the input seen so far, and $q$ says the same for $M_2$.

The product machine has:

$$Q=Q_1\times Q_2$$ $$s=(s_1,s_2)$$

and transition function

$$\delta ((p,q),a)=({\delta }_1(p,a),{\delta }_2(q,a)).$$

The transition rule is fixed: on each input symbol, update both coordinates according to their original DFAs.

The only part that changes from one Boolean operation to another is the set of accepting states.

For example, a state pair $(p,q)$ represents one of four possible situations:

Status in $M_1$	Status in $M_2$	Meaning
rejecting	rejecting	the prefix belongs to neither language
accepting	rejecting	the prefix belongs to $L_1$ only
rejecting	accepting	the prefix belongs to $L_2$ only
accepting	accepting	the prefix belongs to both languages

Thus, the product DFA records exactly the information needed to evaluate any Boolean expression involving membership in $L_1$ and $L_2$.

---

Choosing accepting pairs for Boolean operations

Let $B$ be a Boolean rule with two inputs. For example, $B$ could mean “both are true,” “at least one is true,” or “the first is true and the second false.”

Define the desired language as

$$L_B=\{w\in {\Sigma }^{\ast }\mid B(w\in L_1,w\in L_2)\text{ is true}\}.$$

The product DFA for $L_B$ uses the state set, start state, and transition function already given. Its accepting states are

$$F_B=\{(p,q)\in Q_1\times Q_2\mid B(p\in F_1,q\in F_2)\text{ is true}\}.$$

This single definition gives the common constructions below.

Desired language	Accepting product states
$L_1\cap L_2$	$F_1\times F_2$
$L_1\cup L_2$	pairs where $p\in F_1$ or $q\in F_2$
$L_1\setminus L_2$	pairs where $p\in F_1$ and $q\notin F_2$
$L_1△L_2$	pairs where exactly one coordinate is accepting
strings in both languages or neither	pairs where the two coordinates have the same acceptance status

The last row is sometimes called Boolean equivalence: accept when the two original machines agree about the input.

A useful practical principle follows:

Build the product transitions once; encode the logical operation in the accepting set.

This is more direct than repeatedly redesigning a DFA for every new language expression.

---

The central invariant

Why does this construction work? The proof rests on a precise statement about every input string, not merely the strings we happen to test.

Write ${\delta }^{\ast }$ for the extended transition function, which describes the state reached after reading a whole string. It is defined recursively by

$${\delta }^{\ast }(q,ϵ)=q$$

and

$${\delta }^{\ast }(q,xa)=\delta ({\delta }^{\ast }(q,x),a),$$

where $x\in {\Sigma }^{\ast }$ and $a\in \Sigma$.

For the product DFA, the key lemma is:

$${\delta }^{\ast }((p,q),w)=({\delta }_1^{\ast }(p,w),{\delta }_2^{\ast }(q,w))$$

for every pair $(p,q)$ and every string $w$.

In words: after reading any string, the product DFA is in exactly the pair of states that the component DFAs would reach separately on that same string.

This is the invariant that makes the “parallel simulation” intuition mathematically rigorous.

---

Proving the invariant by induction

A correctness proof should not say merely that the product “obviously runs both machines.” Instead, prove the invariant by induction on the length of the input string.

Base case

Let $w=ϵ$. Then the product DFA has read nothing, so it remains in its initial pair:

$${\delta }^{\ast }((p,q),ϵ)=(p,q).$$

Likewise,

$$({\delta }_1^{\ast }(p,ϵ),{\delta }_2^{\ast }(q,ϵ))=(p,q).$$

Therefore the claim holds for the empty string.

Inductive step

Assume the claim holds for some string $x$. That is, assume

$${\delta }^{\ast }((p,q),x)=({\delta }_1^{\ast }(p,x),{\delta }_2^{\ast }(q,x)).$$

Now consider a string $xa$, where $a\in \Sigma$. By the definition of the extended transition function,

$${\delta }^{\ast }((p,q),xa)=\delta ({\delta }^{\ast }((p,q),x),a).$$

Apply the induction hypothesis:

$${\delta }^{\ast }((p,q),xa)=\delta \left(\right({\delta }_1^{\ast }(p,x),{\delta }_2^{\ast }(q,x)),a).$$

Now apply the definition of the product transition:

$${\delta }^{\ast }((p,q),xa)=({\delta }_1({\delta }_1^{\ast }(p,x),a),{\delta }_2({\delta }_2^{\ast }(q,x),a)).$$

Finally, use the definition of each extended transition function:

$${\delta }^{\ast }((p,q),xa)=({\delta }_1^{\ast }(p,xa),{\delta }_2^{\ast }(q,xa)).$$

Thus the invariant holds for $xa$. By induction, it holds for every $w\in {\Sigma }^{\ast }$.

Notice that proving the lemma for an arbitrary starting pair $(p,q)$, rather than only $(s_1,s_2)$, makes the induction especially clean. The start-state version is an immediate consequence.

---

From the invariant to correctness

Now let $M_B$ denote the product DFA whose accepting set is $F_B$. We prove that it recognizes the intended Boolean combination $L_B$.

For any string $w$,

$$w\in L(M_B)$$

holds exactly when the state reached by $M_B$ is accepting:

$${\delta }^{\ast }((s_1,s_2),w)\in F_B.$$

By the invariant, the reached state is

$$({\delta }_1^{\ast }(s_1,w),{\delta }_2^{\ast }(s_2,w)).$$

By the definition of $F_B$, this pair is accepting exactly when

$$B({\delta }_1^{\ast }(s_1,w)\in F_1,{\delta }_2^{\ast }(s_2,w)\in F_2)$$

is true. But these two membership statements say precisely that

$$w\in L(M_1)$$

and

$$w\in L(M_2),$$

respectively. Therefore,

$$w\in L(M_B)$$

if and only if

$$B(w\in L_1,w\in L_2)$$

is true. Hence,

$$L(M_B)=L_B.$$

That is the complete correctness proof. The proof has two reusable parts:

1. Simulation lemma: prove that the product state tracks the two component states.
2. Acceptance equivalence: show that the selected accepting pairs implement the desired Boolean rule.

For intersection, this final step specializes to

$$w\in L(M)⟺w\in L_1\text{ and }w\in L_2.$$

For difference, it becomes

$$w\in L(M)⟺w\in L_1\text{ and }w\notin L_2.$$

The induction proof is unchanged; only the accepting-state condition changes.

---

Worked example: parity of zeros and ones

Let the alphabet be

$$\Sigma =\{0,1\}.$$

Define:

$$L_0=\{w\in {\Sigma }^{\ast }\mid \text{the number of 0s in w is odd}\}$$

and

$$L_1=\{w\in {\Sigma }^{\ast }\mid \text{the number of 1s in w is odd}\}.$$

A DFA for $L_0$ needs two states: one for an even number of zeros and one for an odd number. Reading $0$ switches between them; reading $1$ leaves the state unchanged. Similarly, a DFA for $L_1$ switches states on $1$ and ignores $0$.

Their product has four states, corresponding to the parity pair:

$$(\text{even }0,\text{ even }1)$$ $$(\text{odd }0,\text{ even }1)$$ $$(\text{even }0,\text{ odd }1)$$ $$(\text{odd }0,\text{ odd }1).$$

The product begins in the even-even state, since the empty string has zero occurrences of both symbols.

The diagram chooses the Boolean equivalence condition as its acceptance rule. It accepts:

$$(\text{even }0,\text{ even }1)$$

and

$$(\text{odd }0,\text{ odd }1).$$

Therefore its language is

$$\{w\in \{0,1{\}}^{\ast }\mid \text{the number of 0s and the number of 1s have the same parity}\}.$$

For instance:

• $ϵ$ is accepted because both counts are even.
• $01$ is accepted because both counts are odd.
• $0$ is rejected because the zero count is odd but the one count is even.
• $001$ is rejected because the zero count is even but the one count is odd.

Crucially, the graph of transitions does not need to change to recognize other Boolean combinations of $L_0$ and $L_1$.

• To recognize $L_0\cap L_1$, accept only the odd-odd state.
• To recognize $L_0\cup L_1$, accept every state except even-even.
• To recognize $L_0\setminus L_1$, accept only odd-zero/even-one.
• To recognize $L_0△L_1$, accept the two states with mismatched parity.

This example captures the whole method: pair states represent simultaneous machine configurations; accepting pairs express the logical condition.

---

A proof-writing checklist

When asked to construct a DFA for a Boolean combination, organize your response in this order:

1. Name the component DFAs and state that they share alphabet $\Sigma$.
2. Define the product DFA completely: state set, alphabet, start state, transition function, and accepting states.
3. State the simulation lemma involving ${\delta }^{\ast }$.
4. Prove the lemma by induction on the length of the input.
5. Write an if-and-only-if acceptance argument that translates product acceptance into the intended Boolean condition.
6. Conclude language equality, not simply that the construction “seems correct.”

Avoid two common gaps:

• Defining product states but never specifying which pairs are accepting.
• Claiming that the DFA “simulates both machines” without proving the invariant for arbitrary strings.

---

Key takeaways

A product DFA has one state for each pair of states from the component DFAs, so it can retain both machines’ information after every input prefix. Its transition function always updates each coordinate independently:

$$\delta ((p,q),a)=({\delta }_1(p,a),{\delta }_2(q,a)).$$

Boolean operations are implemented solely by selecting accepting state pairs according to the relevant truth condition. The proof of correctness rests on an induction showing that the product tracks both original computations exactly, followed by an acceptance equivalence argument.

Next, the course turns from proving languages regular to proving that certain languages are not regular, beginning with the pumping lemma for regular languages.