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

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

• 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 – compute Dec 20 '18 at 14:00

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.

• Nice and compact! – Hendrik Jan Dec 21 '18 at 18:56