patternMinor
Exotic closure of regular languages
Viewed 0 times
languagesexoticregularclosure
Problem
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...
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...
Solution
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.
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.
Context
StackExchange Computer Science Q#152686, answer score: 2
Revisions (0)
No revisions yet.