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
