# Are permutations of context-free languages context-free?

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:

## 1 Answer

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

• A penny just dropped in my head, thanks. – Raphael Apr 15 '13 at 14:45