I’ve encountered the following difficult question that I don’t know how to solve.

$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \sigma_1, \sigma_2, \cdots, \sigma_n\in \Sigma, \\ &\exists \mu_1, \mu_2,\cdots,\mu_n,\zeta_1,\zeta_2,\cdots\, \zeta_n \in\Sigma, \\ &\mu_1\mu_2\cdots\mu_n\in L_2,\sigma_1\mu_1\zeta_1\sigma_2\mu_2\zeta_2...\sigma_n\mu_n\zeta_n\in L_1\}\\ &\cup\{a\mid a\in L_1, a\in L_2, a=\epsilon\}\end{align}$$ where the second set on the right hand side just says that $\epsilon\in L^\wedge\Leftrightarrow \epsilon\in L_1\land \epsilon \in L_2$.

How can we prove $L^\wedge$ is regular using closure properties or a product automaton?

What i tried to do is:

Since $n \geq 0$, we can build $\Sigma^* = \{ \sigma^* | \sigma \in \Sigma \} $ $(\Sigma \cup \Sigma) \to \Sigma^*$, then for some function h we can assign $h(\sigma)=\sigma$ (also $h(\sigma')=\sigma$), so because of homomorphism $h^{-1}(L_1 \cup L_2) = \{ \sigma_1...\sigma_n |\forall 1 \leq i \leq n \to \sigma_i \in \{ \mu_i,\mu_i' \}, \mu_1...\mu_n \in L_1 \cup L_2 \} $,

So if $(L_1 \cup L_2)' = h^{-1}(L_1 \cup L_2) \cap ( \sigma'\Sigma \Sigma')*=\{ \sigma_1'\sigma_2\sigma_3'...\sigma_{n-2}'\sigma_{n-1}\sigma{n}' | \sigma_1... \sigma_n \in (L_1 \cup L_2)$ is also regular

So if for some function $f$, $f(\sigma)=\sigma$ and $f(\sigma')=\epsilon$ $(f|f:(\Sigma' \cup \Sigma) \to \Sigma^*)$

Then $f(L_1' \cup L_2') = \{ \mu_1...\mu_n | σ_1μ_1ξ_1...σ_nμ_nξ_n∈L_1 \cup L_2 = L^∧$ and if regular because of regular languages closure to homomorphism

I know it’s complicated and would appreciate help with it, seeing how to do it correctly (pretty sure I've made some mistakes along the way).

  • $\begingroup$ so let's solve it. it's interesting and difficult and i really want to learn how to solve it correctly. i tried to use homomorphism properties for it, but i think it can be solved in a much easier way $\endgroup$
    – compute
    Commented Dec 20, 2018 at 14:00

2 Answers 2


Let me point you to the proper tools.

The operation of (perfect) shuffle takes two languages $K,L\subseteq \Sigma^*$ and alternatingly takes a symbol from one of them:

$sh(K,L) = \{ a_1b_1a_2b_2 \dots a_kb_k\mid k\ge 0, a_i,b_i\in\Sigma,\text{ where } a_1a_2\dots a_k\in L\text{ and } b_1b_2\dots b_k\in K \}$

This operationhas been discused various times, using both automata and closure properties: Proving regular languages are closed under a form of interleaving, Show that regular languages are closed under Mix operations, and Closure of regular languages to shuffle using closure operations, but probably more.

Then there is the kind-of reverse of this operation, given a language $K\subseteq \Sigma^*$, keep every second letter of its strings:

$2nd(K) = \{ a_2a_4 \dots a_{2k} \mid k\ge 0, a_i\in\Sigma,\text{ for some } a_1a_2\dots a_{2k}\in K \}$

An example for that is is: If L is regular, show that even(L) is also regular. Both solutions there are enlightening.

Also in your case one needs some shuffling (to move the letters from $L_2$ within two other letters in order to compare with $L_1$) and some unshuffling (to keep every first letter of three for $L^{\land}$) but now with three letters/languages rather than two.


Here is a solution using NFAs. Let $A_1,A_2$ be DFAs for $L_1,L_2$. We will construct a new automaton whose states are $Q_1 \times Q_2 \times \{1,2,3\}$. The accepting states are $F_1 \times F_2 \times \{1\}$. The initial state is $(q_{01},q_{02},1)$. The transitions are as follows:

  • $\delta((q_1,q_2,1),\sigma) = \{ (\delta_1(q_1,\sigma),q_2,2) \}$.
  • $\delta((q_1,q_2,2),\epsilon) = \{ (\delta_1(q_1,\sigma), \delta_2(q_2,\sigma), 3) : \sigma \in \Sigma\}$.
  • $\delta((q_1,q_2,3),\epsilon) = \{ (\delta_1(q_1,\sigma),q_2,1) : \sigma \in \Sigma \}$.

I'll let you figure out why this works.

  • $\begingroup$ Nice and compact! $\endgroup$ Commented Dec 21, 2018 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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