Constructing the Cross-Product of 2 DFAs

The Cross-Product of $2$ DFAs is a single DFA which simulates the operation of the $2$ DFAs in parallel. For the sake of simplicity it is assumed that the DFAs share the same alphabet $\Sigma$ .

Problem Statement

Let the two DFAs be defined by $M^1$ and $M^2$

$\begin{align*} M^1 = (Q^1, \Sigma, \delta^1, q_0^1, F^1) \\ M^2 = (Q^2, \Sigma, \delta^2, q_0^2, F^2) \end{align*}$

The languages accepted by these DFAs are $L^1$ and $L^2$ respectively. Using the Cross-Product, a single DFA can be constructed that recognizes

$\begin{align*} L^1 \cup L^2 \\ L^1 \cap L^2 \\ \end{align*}$

Cross-Product

The DFA constructed via Cross-Product is defined as follows

$\begin{align*} M = (Q, \Sigma, \delta, q_0, F) \end{align*}$

where

$\begin{align*} Q & = \{(q_i, q_j)|q_i \in Q^1\text{ and }q_j \in Q^2\} \\ q_0 & = (q_0^1, q_0^2) \\ \delta((q_i, q_j), x) & = (\delta^1(q_i, x), \delta^2(q_j, x)) \\ \end{align*}$

and

Operation	$F$
$L^1 \cup L^2$	$\{(q_i, q_j)\|q_i \in F^1\text{ or }q_j \in F^2\}$
$L^1 \cap L^2$	$\{(q_i, q_j)\|q_i \in F^1\text{ and }q_j \in F^2\}$

Example Problem

It is much easier to follow the Cross-Product construction by writing down the formal definition as a transition table. Consider the two DFAs shown below. The alphabet $\Sigma = \{a, b\}$ . The blue color indicates the start state and the red color indicate(s) the final state(s).

$Q$

The set of states $Q$ for the Cross-Product is defined as

$\begin{equation*} Q = \{(q_i, q_j)|q_i \in Q^1\text{ and }q_j \in Q^2\} \\ \end{equation*}$

Thus, each state in $Q$ is a tuple. The first element comes from the set of states of the first DFA and the second element from the set of states of the second DFA. Thus, there will be a total of $9$ states in $Q$ . These are populated as follows

$q_0$

The start state, $q_0$ , for the Cross-Product is defined as

$\begin{align*} q_0 & = (q_0^1, q_0^2) \\ \end{align*}$

Thus, the start state, $q_0$ , is a tuple. The first element is the start state of the first DFA and the second element is the start state of the second DFA.