Showing $L=\{uw \mid \exists v:uv\in L_{1},vw\in L_{2}\}$ is regular

Question

Let $L_{1,}L_{2}$ be regular languages and define $L:=\{uw \mid \exists v\in\Sigma^{*}:uv\in L_{1},vw\in L_{2}\}$.

I wish to prove that $L$ is regular using only closure properties (such as $L_{1},L_{2}$ is regular then so is $L_{1}\cap L_{2},L1\cup L_{2},L_{1}^{*}$ etc.).

My thoughts: I tried to define a homomorphism $h:\Sigma\cup\Sigma'\to\Sigma^{*}$

$$\forall\sigma\in\Sigma:h(\sigma)=\sigma$$ $$\forall\sigma'\in\Sigma':h(\sigma')=\epsilon$$

Then I tried to look at $h^{-1}(L_{1}),h^{-1}(L_{2})$, I thought about looking at their intersection with the languages $\Sigma^{*}(\Sigma')^{*},(\Sigma')^{*}\Sigma^{*}$ etc to give the words in $h^{-1}(L_{1}),h^{-1}(L_{2})$ the form of $ww'$s.t $w\in L_{1}$ or $w'w$ s.t $w\in L_{2}$.

I am having difficulty to continue, I thought about trying to get to something like $L_{3}(\Sigma')^{*}L_{4}$ where $L_{3}$ is all the prefix of words in $L_{1}$ and $L_{4}$ is all the endings of words in $L_{2}$ and then intersect this with $\Sigma^{*}L_{5}'\Sigma^{*}$ where $L_{5}$ is some language to enforce that the words in $(\Sigma')^{*}$in the expression$L_{3}(\Sigma')^{*}L_{4}$ will be such that if I remove all the tags (using a homomorphism) I would get $L$.

How can I show $L$ is regular using only closure properties ?

Answer 1

Let $\underline \Sigma := \{ \underline a : a \in \Sigma \}$ be a disjoint copy of $\Sigma$, assume $<$ and $>$ are symbols not already present in $\Sigma$ and define a homomorphism $h: \Sigma \cup \underline \Sigma \cup \{<,>\} \to \Sigma$ by \begin{align*} a &\mapsto a,\\ \underline a &\mapsto a,\\ < &\mapsto \varepsilon,\\ > &\mapsto \varepsilon.\\ \end{align*} Then \begin{align*} K &:= \{ u \text{<}\underline v \text{>} w : uv \in L_1, vw \in L_2 \}\\ &= \Sigma^* \text{<}\underline{\Sigma}^*\text{>} \Sigma^* \cap h^{-1}(L_1)\text{>}\Sigma^* \cap \Sigma^* \text{<}h^{-1}(L_2) \end{align*} is regular by the closure properties of regular languages, and so is $L$ since it is the homomorphic image of $K$ by deleting the symbols from $\underline \Sigma$ and $\{<,>\}$.

Answer 2

Another way is to make 3 distinct copies $\Sigma_i$ of $\Sigma$, and define the morphisms $h_i : \Sigma_1 \cup \Sigma_2 \cup \Sigma_3 \to \Sigma^*$, by $a_i \mapsto \varepsilon ; a_j \mapsto a$ for $j \neq i$ ($h_i$ simply erases the letters from $\Sigma_i$)

Then $L = h_2(\Sigma_1^* \Sigma_2^* \Sigma_3^* \cap h_3^{-1}(L_1) \cap h_1^{-1}(L_2))$

Answer 3

There is a simple solution using Nerode's theorem. Given a language $L$ and a word $u$, the left [right] quotient of $L$ by $u$ are defined by $u^{-1}L = \{v \mid uv \in L\}$ and $Lu^{-1} = \{v \mid vu \in L\}$.

Nerode's theorem states that a language is regular if and only if it as finitely many left (respectively right) quotients. Further, the quotients of a regular language are also regular. That being said, your language is equal to $$ L = \bigcup_{v \in A^*} (L_1v^{-1})(v^{-1}L_2) $$ and since $L_1$ and $L_2$ are regular, this apparently infinite union can be rewritten as a finite union. To be precise, there are only finitely many pairs of the form $(L_1v^{-1},v^{-1}L_2)$. Thus $L$ is regular.