Proving a language comprised of 2 languages is regular(with suffix and prefix)

Question

I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:

$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\sigma_n\mu_nv\}$$

• $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$

I don't understand how to prove if because of the suffix and prefix(u,v accordingly).

If it weren't for u,v what I think I would've done is building an automaton(Deterministic finite automaton): $A=\left(Σ,Q1xQ2x\left\{1,2\right\},\left(q01,q02,2\right),F1xF2x2,δ\right)$, Ending in accepting iff both automatons that accept each language end in an accepting state, and $L_2$ needs to be after $L_1$ from the language's description. However, I don't know how to deal with the u,v in the beginning and in the end. I am not sure how to configure it correctly to prove $L^\frown$ is regular.

Would very much appreciate your assistance with it.

Answer 1

Your language is the concatenation $\Sigma^* L \Sigma^*$, where $L$ is the so-called perfect shuffle of $L_1$ and $L_2$. There are at least two proofs that the perfect shuffle of two regular languages is regular on this site: using automata and using closure operations.

If you are hell-bent on constructing an automaton for $\Sigma^* L \Sigma^*$, start with one for $L$, then follow the automata proof of closure under concatenation (which constructs an NFA).