Proving regular languages are closed under a form of interleaving - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:32:44Z https://cs.stackexchange.com/feeds/question/42347 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/42347 3 Proving regular languages are closed under a form of interleaving OrWn https://cs.stackexchange.com/users/33488 2015-05-09T13:22:44Z 2015-05-09T23:08:11Z <p>I've got the following definitions:</p> <p>$$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$</p> <p>when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means the $i$-th letter in $w$.</p> <p>$$\mathrm{Interleave}\,(L_1,L_2)\ \ = \!\!\!\!\bigcup_{\substack{x\in L_1,\ y\in L_2,\\ |x|=|y|}}\!\!\!\! \mathrm{Interleave}\,(x,y)$$ when both $L_1$ and $L_2$ are languages.</p> <p>I have to prove that if I know that $L_1$ and $L_2$ are both regular languages, $\mathrm{Interleave}\,(L_1,L_2)$ is a regular language as well.</p> <p>I have absolutely no idea how to do it .</p> <p>Thanks in advance.</p> https://cs.stackexchange.com/questions/42347/-/42349#42349 3 Answer by David Richerby for Proving regular languages are closed under a form of interleaving David Richerby https://cs.stackexchange.com/users/9550 2015-05-09T14:24:26Z 2015-05-09T14:24:26Z <p><strong>Hint.</strong> Because $L_1$ and&nbsp;$L_2$ are both regular, you know they're accepted by NFAs (or DFAs; it doesn't matter) $M_1$ and&nbsp;$M_2$, respectively. To show that $\mathrm{Interleave}\,(L_1,L_2)$ is regular, show that it's accepted by some NFA&nbsp;$M$. For each character it receives, $M$&nbsp;can decide to act either like&nbsp;$M_1$ or like&nbsp;$M_2$.</p> https://cs.stackexchange.com/questions/42347/-/42353#42353 1 Answer by babou for Proving regular languages are closed under a form of interleaving babou https://cs.stackexchange.com/users/8321 2015-05-09T18:06:30Z 2015-05-09T20:03:23Z <p><strong>Any family of language that is a <a href="http://en.wikipedia.org/wiki/Abstract_family_of_languages" rel="nofollow">trio</a> is closed under interleaving with a regular set.</strong></p> <p>This includes of course interleaving of 2 regular sets, since regular sets form a trio.</p> <h2>Proving the result (and more) only with closure properties</h2> <p><strong>Note:</strong> <em>I created the definitions below for the purpose of this question. I do not know whether there are established definitions for this, which might exist under another name.</em></p> <p>The purpose of this approach is to avoid any complex construction of automaton. But we need at least one specific operation to account for dealing with several strings at the same time. And, as an unexpected benefit, the end result is much more general (<em>this is actually more to be expected from proofs based on closure properties</em>). However, the proof is centered on the question asked, and only includes remarks to show how it generalizes.</p> <p>Consider two alphabets $\Sigma_i$ for $i=1,2$. We can consider their product $\Sigma_1\times\Sigma_2=\{(a_1,a_2)\mid a_1\in\Sigma_1\wedge a_2\in\Sigma_2\}$ as a new alphabet, where the symbols are pairs of symbols of $\Sigma_1$ and $\Sigma_2$.</p> <p>Similarly, with 3 alphabets, we can build an alphabet of triples (instead of pairs). We ignore the trivial issue of associativity in using pairs to build triples, or $n$-tuples, here and in the rest of this answer.</p> <p>Now, given two strings $x\in\Sigma^*$ and $y\in\Pi^*$ such that $|x|=|y|$ we can define the conflation of these two strings as the string $z=\mathrm{Conflate}\,(x,y)\in(\Sigma\times\Pi)^*$ with the same size, such that $\forall i\in[1,|x|], z_i=(x_i,y_i)$.</p> <p>We can similarly conflate $n$ strings of equal length into a single string of $n$-tuples of symbols ... but we will not go beyond $n=3$.</p> <p>Finally, given two languages $L_1\subseteq\Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$ we can define the conflation of these two languages:</p> <p>$$\mathrm{Conflate}\,(L_1,L_2)=\{\mathrm{Conflate}\,(x,y)\mid |x|=|y|\wedge x\in L_1 \wedge y\in L_2\}$$</p> <p>We can also conflate similarly any number of languages, to produce a language on the cross product of their alphabets.</p> <p>This $\mathrm{Conflate}$ operation has many simple properties, that are rather trivial to prove.</p> <p>Given two alphabets $\Sigma_1$ and $\Sigma_2$ and two languages $L_1\subseteq\Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$:</p> <ul> <li><p>$\mathrm{Conflate}\,(L_1,L_2)\subseteq(\Sigma_1\times\Sigma_2)^*$</p></li> <li><p>$\mathrm{Conflate}\,(L_1,\Sigma_2^*)$ is regular iff $L_1$ is regular</p></li> <li><p>$\mathrm{Conflate}\,(\Sigma_1^*,L_2)$ is regular iff $L_2$ is regular<br> The proof uses a projection homomorphism that keep only the $L_1$ or the $L_2$ component of the conflation.</p></li> <li><p>side note: the above is also true for context-free, and more generally families of languages closed under non-erasing homomorphism and inverse homomorphism (such as <a href="http://en.wikipedia.org/wiki/Abstract_family_of_languages" rel="nofollow">trios</a>). For example, if $\mathcal F$ is a trio, and $L$ is a language, and $\Sigma$ and alphabet (not necessarily the alphabet of $L$), then $\mathrm{Conflate}\,(L,\Sigma^*)\in\mathcal F\;$ iff $\;L\in\mathcal F$.</p></li> <li><p>$\mathrm{Conflate}\,(L_1,L_2)= \mathrm{Conflate}\,(L_1,\Sigma_2^*) \cap \mathrm{Conflate}\,(\Sigma_1^*,L_2)$</p></li> <li><p>Hence, if $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular.</p></li> </ul> <p>Now we consider also the alphabet $B=\{0,1\}$, and the alphabet cross-product $\Sigma_1\times\Sigma_2\times B$, and we define on this alphabet the substitution $\sigma$ as follows:</p> <p>$\forall (a_1,a_2,b)\in(\Sigma_1\times\Sigma_2\times B),\; \sigma((a_1,a_2,b))=\;($ if $b=0$ then $a_1$ else $a_2)$.</p> <p>If $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular, and thus $\mathrm{Conflate}\,(\mathrm{Conflate}\,(L_1,L_2),B^*)$ is regular, since $B^*$ is.</p> <p>Applying the substitution $\sigma$, since regular sets are closed under substitution, we know that the language $\sigma(\mathrm{Conflate}\,(\mathrm{Conflate}\,(L_1,L_2),B^*))$ is regular.</p> <p>But it can fairly easily be proved that</p> <p>$$\mathrm{Interleave}\,(L_1,L_2)=\sigma(\mathrm{Conflate}\,(\mathrm{Conflate}\,(L_1,L_2),B^*))$$</p> <p>Hence $\mathrm{Interleave}\,(L_1,L_2)$ is regular.</p> <p>The interesting point here is that, with nearly no further work, we can prove identically that many families of languages, context-free for example, and more generally trios (hence also AFLs), are closed under $\mathrm{Interleave}$ composition with regular languages, notably because the substitution $\sigma$ is non-erasing. This essentially follows from the fact that <a href="http://en.wikipedia.org/wiki/Abstract_family_of_languages" rel="nofollow">trios are closed under inverse homomorphism, under intersection with regular sets, and under non-erasing homomorphism</a>.</p>