# Exotic closure of regular languages

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

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.

• This looks good, but how can one justify the $\tau\left(q,\#\right)$ set definition? We have no knowledge about L2. How can I construct this set with general L1, L2? Jun 28 at 18:38
• Please come to chat with me. Jun 28 at 20:10
• Exercise: Prove $L$ is regular by demonstrating the finiteness of Myhill–Nerode classes. Jun 28 at 21:57