Note that this is not shuffle but perfect shuffle, defined as follows:

Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle of $w$ and $x$ is defined as $a_{1}b_{1}a_{2}b_{2} \ldots a_{n}b_{n}$.

So the question is: are context free languages closed under perfect shuffle?

  • 1
    $\begingroup$ Do you define the perfect shuffle as an unary or binary operation? I.e. are $w$ and $x$ from the same regular language or from two different regular languages? $\endgroup$
    – Gaste
    Nov 2 '14 at 23:48
  • $\begingroup$ So this is not actually shuffling but interleaving. $\endgroup$ Nov 3 '14 at 0:52
  • $\begingroup$ No. Actually a in w and b in x are both characters. So w and x are both strings formed by ai and bi. $\endgroup$
    – ForSol
    Nov 3 '14 at 1:26
  • 1
    $\begingroup$ @DavidRicherby Interleaving seems good terminology, but perfect shuffle is sometimes used. $\endgroup$ Nov 3 '14 at 22:00

Nope. Shuffle $\{ a^n b^{2n} \mid n\ge1\}$ with $\{ a^{2n} b^n \mid n\ge1\}$ .

  • $\begingroup$ Thank you. So we will get {a^n(ba)^nb^n | n>=1 }. How can I prove that this is not context free $\endgroup$
    – ForSol
    Nov 3 '14 at 1:31
  • 1
    $\begingroup$ Its almost the same proof as for $\{a^n b^n c^n \mid n \geq 1\}$ $\endgroup$
    – Mike B.
    Nov 3 '14 at 7:29

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.