[Solved]: Are permutations of context-free languages context-free?

Problem Detail: 

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ context-free?

I found two papers dealing with similar, but not identical, questions:

• Generating all permutations by context-free grammars in Chomsky normal form by Asveld (2003) deals with finite languages.

• Permutations are not context-free: An application of the interchange lemma by Main (1982) deals with "permutation languages", i.e. sets of strings of the form $w x p(x) z$, where $p(x)$ is a any permutation of $x$. Also, the result is limited to alphabets with 16 symbols.

Asked By : Erel Segal-Halevi

Answered By : Hendrik Jan

Start with simple context-free (or even regular) languages, and see what happens. For instance determine $p(L)$ for $L = (ab)^*$ and $L=(abc)^*$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11329