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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.