This question already has an answer here:

Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA.

Prove that the following language is regular, by making an appropriate NFA for it:

𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎𝑛𝜎𝑛′ |𝜎1𝜎2…𝜎𝑛∈𝐿1,𝜎1′𝜎2′…𝜎𝑛′ ∈𝐿2} (Meaning, the language of all words in which the letters on the even positions (starting from 0) form a word from L2 and the letters on the odd positions form a word from L1.

Would appreciate help with that. Thank you.


marked as duplicate by Apass.Jack, Evil, Hendrik Jan, Yuval Filmus regular-languages May 3 at 23:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Just for a fixed n? $\endgroup$ – Dandelion May 3 at 11:14
  • $\begingroup$ The letters in the even position are words from L2? $sigma$ is a word or a letter? $\endgroup$ – Dandelion May 3 at 11:16
  • $\begingroup$ All sigmas are letters. What I meant is that the language L3 contains all words, in which all the letters on the even positions form a word from L2, and all the letters on the odd positions form a word from L1. $\endgroup$ – Asher Castro May 3 at 11:21
  • $\begingroup$ Here is another similar question closure of regular languages to shuffle using closure operations. $\endgroup$ – Apass.Jack May 3 at 14:30

The idea is like the production of two DFAs. Let two DFAs be $M_1 = (Q_1, \Sigma , \delta_1, q_{01}, F_1)$ and $M_2 = (Q_2, \Sigma , \delta_2, q_{02}, F_2)$. Define NFA $M = (Q, \Sigma , \delta, q_0, F)$ to have:

$ Q = Q_1 \times Q_2 \times \{0,1\}$

$ \delta((q_1,q_2,0), a) = (\delta(q_1,a),q_2,1) \forall q_1 \in Q_1, q_2 \in Q_2, a \in \Sigma$

$ \delta((q_1,q_2,1), a) = (q_1,\delta(q_2,a),0) \forall q_1 \in Q_1, q_2 \in Q_2, a \in \Sigma$

$ q_0 = (q_1,q_2,0)$

$ (q_1,q_2,0) \in F \ \text{iff} \ q_1 \in F_1 \ \text{and} \ q_2 \in F_2$

Note that the 0 or 1 is just indicating moving turn! In a final state, the turn has to be 0 meaning $M1$'s turn!


You can make the DFAs for L1' and L2' where there is a letter inserted between every word from L1 and L2 resp.

You do this by splitting every state $q_i$ in 2 ${q_{i1}, q_{i2}}$ where $q_{i1}$ gets all incoming transitions and $q_{i2}$ gets all outgoing transitions and putting a transition between them that consumes 1 symbol. Final states get split into 2 final states.

The start state of L1' is the $q_02$ the starting state of L2' is $q_01$. That is L1' starts in the start state with all the outgoing transitions and L2' starts in the start state with all incoming transitions.

L3 then is the union between L1' and L2'.


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