Prove that $R_1 \times R_2$ is a regular language for $R_1, R_2$ regular

Question

Let A and B be two sets. The cross products of A and B are defined as : AxB={(a,b): a belongs to A and b belongs to B }. Assume R1 and R2 are regular languages over an input alphabet Σ={a,b}. Prove R1xR2 is a regular language

Answer 1

Let $A = R_{1}$ and $B = R_{2}$. Let $M(A)$ and $M(B)$ be the finite state machines accepting $A$ and $B$ respectively. Define $M(A \times B)$ to be the machine with states $Q_{A} \times Q_{B}$, transition function $\delta_{A} \times \delta_{B}$ and final states $F_{A} \times F_{B}$. Argue that this machine captures $A \times B$ exactly.

Without loss of generality, suppose each final state has an $\epsilon$ transition looping to itself. So $\delta_{i}(f, \epsilon) = f$ for every $f \in F_{i}$. This accounts for differences in string lengths.

Now suppose $(a, b) \in A \times B$. This implies $a \in A$ and $b \in B$ and $A, B$ are regular, there is a sequence of transitions $(\delta_{A}(q_{x_{i}}, a_{i}))_{i=1}^{n}$ with each $q_{x_{i}} \in Q_{A}$ and $(\delta_{B}(q_{y_{i}}, b_{i}))_{i=1}^{n}$ with each $q_{y_{i}} \in Q_{B}$ such that $M(A)$ terminates in an accepting halt state and $M(B)$ terminates in an accepting halt state. By construction of $M(A \times B)$, we take $(\delta_{A \times B}( (q_{x_{i}}, q_{y_{i}}), (a_{i}, b_{i}))_{i=1}^{n}$, which terminates in a state in $F_{A} \times F_{B}$ by construction.

The converse takes a sequence of product states and then breaks them up. It's just working backwards.

Answer 2

Consider that if you define disjoint alphabets for $R_1$ and $R_2$, then, given regular expressions for the languages $R_1$ and $R_2$, all you need to do is concatenate the two regular expressions for $R_1$ and $R_2$ (using their different alphabets) and then, because they use different alphabets, you can tell for each string in this bizarre regular expression, which part of the string belongs to $R_1$ and which part belongs to $R_2$. It's fairly easy to see this is equivalent to recognizing $R_1 \times R_2$.