# Zigzag concatenation of two languages

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$$?

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*}