0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Just for a fixed n? $\endgroup$
    – Dandelion
    May 3, 2019 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, 2019 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, 2019 at 11:21
  • $\begingroup$ Here is another similar question closure of regular languages to shuffle using closure operations. $\endgroup$
    – John L.
    May 3, 2019 at 14:30

2 Answers 2

Reset to default
0
$\begingroup$

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!

Improve this answer
$\endgroup$
0
$\begingroup$

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'.

Improve this answer
$\endgroup$

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