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?

  • $\begingroup$ 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. $\endgroup$
    – orlp
    Commented Dec 13, 2019 at 4:04
  • $\begingroup$ What's a basic idea to construct and show that they are closed in that operations? $\endgroup$ Commented Dec 13, 2019 at 4:32

1 Answer 1


Express the two languages as NFA. Use a product construction. Think carefully about what transitions should exist in the product automaton.

  • $\begingroup$ could you help me a bit about product construction and the transition? $\endgroup$ Commented Dec 13, 2019 at 8:50
  • 1
    $\begingroup$ @unsure_automata, nope. It's your exercise. I've given you a huge hint. Now you should get to have the pleasure of working out the details. $\endgroup$
    – D.W.
    Commented Dec 13, 2019 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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