How to prove certain parts of one regular language restricted by another regular language is also regular?

Question

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

Answer 1

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.

Answer 2

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.