2 added 503 characters in body
source | link

This includes of course interleaving of 2 regular sets, since regular sets form a trio.

Proving the result (and more) mostlyonly with closure properties

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

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 (this is actually more to be expected from proofs based on closure properties). However, the proof is centered on the question asked, and only includes remarks to show how it generalizes.

  • $\mathrm{Conflate}\,(L_1,L_2)\subseteq(\Sigma_1\times\Sigma_2)^*$

  • $\mathrm{Conflate}\,(L_1,\Sigma_2^*)$ is regular iff $L_1$ is regular

  • $\mathrm{Conflate}\,(\Sigma_1^*,L_2)$ is regular iff $L_2$ is regular
    The proof uses a projection homomorphism that keep only the $L_1$ or the $L_2$ component of the conflation.

  • 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 trios). 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$.

  • $\mathrm{Conflate}\,(L_1,L_2)= \mathrm{Conflate}\,(L_1,\Sigma_2^*) \cap \mathrm{Conflate}\,(\Sigma_1^*,L_2)$

  • Hence, if $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular.

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 trios are closed under inverse homomorphism, under intersection with regular sets, and under non-erasing homomorphism.

This includes of course interleaving of 2 regular sets.

Proving the result (and more) mostly with closure properties

Note: I created the definitions below for the purpose of this question. I do not know whether there are established definitions for this.

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 (this is actually more to be expected from proofs based on closure properties).

  • $\mathrm{Conflate}\,(L_1,L_2)\subseteq(\Sigma_1\times\Sigma_2)^*$

  • $\mathrm{Conflate}\,(L_1,\Sigma_2^*)$ is regular iff $L_1$ is regular

  • $\mathrm{Conflate}\,(\Sigma_1^*,L_2)$ is regular iff $L_2$ is regular

  • 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 trios)

  • $\mathrm{Conflate}\,(L_1,L_2)= \mathrm{Conflate}\,(L_1,\Sigma_2^*) \cap \mathrm{Conflate}\,(\Sigma_1^*,L_2)$

  • Hence, if $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular.

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 trios are closed under homomorphism, under intersection with regular sets, and under non-erasing homomorphism.

This includes of course interleaving of 2 regular sets, since regular sets form a trio.

Proving the result (and more) only with closure properties

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

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 (this is actually more to be expected from proofs based on closure properties). However, the proof is centered on the question asked, and only includes remarks to show how it generalizes.

  • $\mathrm{Conflate}\,(L_1,L_2)\subseteq(\Sigma_1\times\Sigma_2)^*$

  • $\mathrm{Conflate}\,(L_1,\Sigma_2^*)$ is regular iff $L_1$ is regular

  • $\mathrm{Conflate}\,(\Sigma_1^*,L_2)$ is regular iff $L_2$ is regular
    The proof uses a projection homomorphism that keep only the $L_1$ or the $L_2$ component of the conflation.

  • 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 trios). 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$.

  • $\mathrm{Conflate}\,(L_1,L_2)= \mathrm{Conflate}\,(L_1,\Sigma_2^*) \cap \mathrm{Conflate}\,(\Sigma_1^*,L_2)$

  • Hence, if $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular.

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 trios are closed under inverse homomorphism, under intersection with regular sets, and under non-erasing homomorphism.

1
source | link

Any family of language that is a trio is closed under interleaving with a regular set.

This includes of course interleaving of 2 regular sets.

Proving the result (and more) mostly with closure properties

Note: I created the definitions below for the purpose of this question. I do not know whether there are established definitions for this.

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 (this is actually more to be expected from proofs based on closure properties).

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

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.

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

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

Finally, given two languages $L_1\subseteq\Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$ we can define the conflation of these two languages:

$$\mathrm{Conflate}\,(L_1,L_2)=\{\mathrm{Conflate}\,(x,y)\mid |x|=|y|\wedge x\in L_1 \wedge y\in L_2\}$$

We can also conflate similarly any number of languages, to produce a language on the cross product of their alphabets.

This $\mathrm{Conflate}$ operation has many simple properties, that are rather trivial to prove.

Given two alphabets $\Sigma_1$ and $\Sigma_2$ and two languages $L_1\subseteq\Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$:

  • $\mathrm{Conflate}\,(L_1,L_2)\subseteq(\Sigma_1\times\Sigma_2)^*$

  • $\mathrm{Conflate}\,(L_1,\Sigma_2^*)$ is regular iff $L_1$ is regular

  • $\mathrm{Conflate}\,(\Sigma_1^*,L_2)$ is regular iff $L_2$ is regular

  • 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 trios)

  • $\mathrm{Conflate}\,(L_1,L_2)= \mathrm{Conflate}\,(L_1,\Sigma_2^*) \cap \mathrm{Conflate}\,(\Sigma_1^*,L_2)$

  • Hence, if $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular.

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:

$\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)$.

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.

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.

But it can fairly easily be proved that

$$\mathrm{Interleave}\,(L_1,L_2)=\sigma(\mathrm{Conflate}\,(\mathrm{Conflate}\,(L_1,L_2),B^*))$$

Hence $\mathrm{Interleave}\,(L_1,L_2)$ is regular.

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 trios are closed under homomorphism, under intersection with regular sets, and under non-erasing homomorphism.