Exotic closure of regular languages

Question

Let $L_1 \subseteq \{0,1\}^{*}$ be a regular language, and let $L_2 \subseteq \{0,1\}^{*}$ be some (not necessarily regular) language. Show that $$L=\left\{ \sigma_{1}\#\sigma_{2}\dots\#\sigma_{n}\mid\substack{n\geq1\\ \sigma_{i}\in\left\{ 0,1\right\} \\ \exists w_{1},\dots w_{n-1}\in L_{2}\quad\sigma_{1}w_{1}\sigma_{2}w_{2}\dots w_{n-1}\sigma_{n}\in L_{1} } \right\} $$ is regular.

I tried thinking about the Myhill–Nerode classes, and about closure under homomorphism, and homomorphism inverse, but I didn't achieve any result. I also tried thinking about $L_1$'s DFA and trying to squeeze NFA in between edges, but I don't have an NFA for L2...

Answer 1

Because of the choices for $w_i$, it is easier to track the conditions if we include non-determinism.

---

Let $L_1$ be accepted by DFA $D=(Q, \{0,1\}, \delta, q_0, F)$.

Let NFA $N=(Q\sqcup Q_\#\sqcup\{\text{dead}\}\}, \{0,1,\#\},\tau, (q_0)_\#, F)$, where

• $Q_\#$ is a $\#$-tagged copy of $Q$, i.e., $Q_\#=\{q_\#\mid q\in Q\}$.

• For all $\sigma\in\{0,1\}$ and for all $q\in Q$,
      $\tau(q_\#, \sigma) =\{\delta(q, \sigma) \}$,
      $\tau(q, \#) = \{r_\# \mid \exists w\in L_2 \text{ such that } \delta(q, w )=r\}$, and
      $\tau(q_\#, \#)=\tau(q, \sigma)=\tau(\text{dead}, \sigma)=\tau(\text{dead}, \#)=\{\text{dead}\}$.

  In plain words, when it is running against an input, for each executing path, $N$ will either alternate its state between tagged states and nontagged states, ending up in $F$ possibly, or go into state $\text{dead}$, a trapped state. In particular, when $N$ in an untagged state reads a $\#$, it can move to any corresponding tagged state as if it were $D$ reading any word in $L_2$.

It is a routine exercise to verify the regular language accepted by $N$ is $L$. So $L$ is regular.