Prove that Language is Regular Using Closure Properties

Question

Given: $L_1, L_2$ are regular languages. We define the language $L$.

$L = \{uw \mid \exists v \in \Sigma^*, uv \in L_1, vw \in L_2\}$.

I need to prove that $L$ is a regular language using only Closure Properties.

Answer 1

Given a language $K$ of $A^*$ and a word $v\in A^*$, recall that $$ v^{-1}K = \{ u \in A^* \mid vu \in K\} \quad \text{and} \quad Kv^{-1} = \{ u \in A^* \mid uv \in K\} $$ If $K$ is regular, then $v^{-1}K$ and $Kv^{-1}$ are regular. Furthermore, there are only finitely many sets of the form $v^{-1}K$ (respectively $Kv^{-1}$). Now your language can be written as $$ L = \bigcup_{v\in A^*} (L_1v^{-1}) (v^{-1}L_2) $$ and hence $L$ is regular.