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, 2014 at 23:48
  • $\begingroup$ So this is not actually shuffling but interleaving. $\endgroup$ Nov 3, 2014 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, 2014 at 1:26
  • 1
    $\begingroup$ @DavidRicherby Interleaving seems good terminology, but perfect shuffle is sometimes used. $\endgroup$ Nov 3, 2014 at 22:00

1 Answer 1


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, 2014 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, 2014 at 7:29

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.