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

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.

• I must be missing something. Isn't $L⌢$ just $Σ∗$? Set $u = w$ and $n =0$. Oct 23, 2019 at 7:39

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