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


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

  • $\begingroup$ 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? $\endgroup$
    – Xiobiq
    Jun 28 at 18:38
  • $\begingroup$ Please come to chat with me. $\endgroup$
    – John L.
    Jun 28 at 20:10
  • $\begingroup$ Exercise: Prove $L$ is regular by demonstrating the finiteness of Myhill–Nerode classes. $\endgroup$
    – John L.
    Jun 28 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.