# Showing that the class of regular languages are closed under merging / modified shuffle

Consider $$ab$$ and $$cd$$ which are two words. We merge these two into 6 possibilities: $$abcd, acbd, acdb, cabd, cadb, cdab$$

So in general, a merge of words/sequences $$x, y ∈ Σ∗$$ , is a word of length $$|x| + |y|$$ with both $$x$$ and $$y$$ as disjoint subsequences in it.

For two languages $$L1$$ and $$L2$$ their merge is defined as the set of all possible merges of two words $$x ∈ L1, y ∈ L2$$.

So basically, a merge is a modified shuffle and should be of length that of the sum of the length of two languages, and should also be in order (see $$ab$$ and $$cd$$ example, as $$b$$ could not come before $$a$$).

I was thinking of just connecting the states of all $$L1$$ and $$L2$$ but this seems wrong as if you connect them all like a fully connected graph, one can jump and go back which is not acceptable.

What's a basic idea on the construction I could do to prove this?

• If either $L1$ or $L2$ are required to be finite your proposed closed property holds but I'm not sure for infinite languages at all.
– orlp
Dec 13 '19 at 4:04
• What's a basic idea to construct and show that they are closed in that operations? Dec 13 '19 at 4:32