Zigzag concatenation of two languages

Question

Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular: $$ \{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \Sigma,a_1\ldots a_k \in A, b_1\ldots b_k \in B\}. $$

However I simply do not understand how I'm supposed to do this. Simply put, my confusion is what $w = a_i b_i$ means. Is it concatenation? Does it mean that the word $w$ is the concatenation of $a=a_1\ldots a_k$ with $b=b_1 \ldots b_k$?

Answer 1

Since languages $A$ and $B$ are regular, we can assume there are DFAs $$ M_A = \{Q_A, \Sigma, \delta_A, s_A, F_A\} ~~\text{and}~~ M_B = \{Q_B, \Sigma, \delta_B, s_B, F_B\} $$ that recognize them, respectively. Let's call the zig-zag lanuage $Z$. It is easy to see that the alphabet of $Z$ is $\Sigma$.

We will construct a DFA, $M_Z = \{Q_Z, \Sigma, \delta_Z, s_Z, F_Z\}$, for $Z$.

Set of states

$M_Z$ must be such that it will alternately apply $\delta_A$ and $\delta_B$ each time it reads a character from the input string. For that, it must be able to track all possible combinations between states of $M_A$ and $M_B$, as well as which of the two transition functions it should apply on the next transition. We will use 0 to represent that the next transition should be a $\delta_A$-move and $1$ for a $\delta_B$-move. Altogether, we have $Q_Z = Q_A \times Q_B \times \{0,1\}$.

Initial state

Clearly, the initial state of $M_Z$ is $s_Z = (s_A, s_B, 0)$.

Accepting states

For a state $q_f = (q_A, q_B, i)$ of $M_Z$ to be accepting, both $q_A$ and $q_B$ must be accepting states of $M_A$ and $M_B$, respectively. This is to satisfy the conditions $a_1\ldots a_k\in A$ and $b_1\ldots b_k\in B$ in the definition of $Z$. In addition, the last transition before reaching $q_f$ should be a $\delta_B$-move, therefore the next transition (if there is one) is expected to be a $\delta_A$-move, represented with $i = 0$. So, the set of accepting states is $F_Z = F_A\times F_B\times\{0\}$.

Transition function: Here is where the alternating behavior of $M_Z$ is constructed.

If the DFA is in a 0-state, then it should perform a $\delta_A$-move, leading to a 1-state. The DFA still needs to remember the (non-active, for now) state of $M_B$. A similar behavior, but with 0 and 1 switched, is adopted for transitions from 1-states. \begin{align*} \delta_Z((q_A, q_B, 0), x) &= (\delta_A(q_A, x), q_B, 1)\\ \delta_Z((q_A, q_B, 1), x) &= (q_A, \delta_B(q_B, x), 0) \end{align*}