1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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
    Dec 13 '19 at 4:04
  • $\begingroup$ What's a basic idea to construct and show that they are closed in that operations? $\endgroup$
    – unsure_automata
    Dec 13 '19 at 4:32
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ could you help me a bit about product construction and the transition? $\endgroup$
    – unsure_automata
    Dec 13 '19 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. ♦
    Dec 13 '19 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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