# Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$

Prove that both regular languages and CFLs aren't closed under $Perm(L)$.

I've tried to use several well-known languages (like $\{0^n1^n\}$) and applying $Perm(L)$ and afterward manipulate them or using the pumping lemma in order to get a contradiction, but nothing worked out.

• You are aware that you should do your homework on your own?
– Raphael
May 19, 2015 at 14:04
• May 24, 2015 at 2:14

1. For regular languages, consider $Perm((01)^*) \cap 0^* 1^*$.
2. For context-free languages, consider $Perm(0^n 1^n 2^m 3^m) \cap 0^* 2^* 1^* 3^*$.
• And also $Perm((012)^*) \cap 0^*1^*2^*$, which jumps from regular ouside context-free. May 19, 2015 at 13:59