why is this language regular?(complicated) I am trying to understand why is the following language comprised of two languages $L_1$, $L_2$($L_1$, $L_2$ are regular) is a regular language:
$L_1$, $L_2$ are languages over the same $\Sigma$. $$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\sigma_n\mu_nv\}$$ where 


*

*$u,v \in \Sigma^*$

*$0\leq n$, for every i($1\leq i \leq n$): $\sigma_i,\mu_i \in \Sigma$

*$\sigma_1...\sigma_n \in L_1$

*$\mu_1...\mu_n \in L_2$
Why is $L^\frown$ regular? 
i don't understand the u,v in the beginning and end of word w.
if it didn't include u,v, i would've built an automaton (finite) that accepts $L^\frown$. so basically, this is the automaton i would've used without u,v: 
$$A = (\Sigma, Q_1 x Q_2 x {1,2},(q_{01},q_{02},2),F_1 x F_2 x{2}, \delta)$$ and $\epsilon \in L$ iff epsilon is in both languages($L_1, L_2$)
 A: Consider languages over the alphabet $\Sigma$. Assume that we have a regular language $L$ and an automaton $A = ( \Sigma, Q, q_0, F, \delta )$ that accepts $L$. Now consider the language $L' = \{ uw | u \in \Sigma^*, w \in L' \}$. The following nondeterministic automaton accepts $L'$: $A' = (\Sigma, Q \cup q', q', F, \delta \cup \{ (q', a) \rightarrow \{ q' q_0 \} | a\in \Sigma\} )$. Why does this work. Well consider any word $uw, u \in \Sigma^*, w \in L'$: Then there is an execution of the word on $A'$ where we first do $|u| - 1$ transitions from $q'$ to $q'$ and then one transition to $q_0$. From there on we are left with $w$ and we are in $q_0$ and thus we accept $\iff$ $w \in L$.
Consider any word that is not in $L'$: In order to not belong to $L'$ the word cannot have a suffix which is in $L$. But by definition of our automaton it only accepts words which have a suffix which is in $L$.
Hope this helps. For the case of the suffix $v$ you can replace all accepting states by a new accepting state and then introduce "edges" from all previous accepting states to that new accepting state. In that new accepting state you add an "edge" to itself for all $a \in \Sigma$.
Edit: I'm sorry it is not entirely correct what I wrote. For the empty prefix this construction does not work. You would have to allow zero transitions in order to make it work. Otherwise you could it without the new state $q'$ and just introduce a loop at $q_0$.
