[Solved]: Prove that regular languages and context-free languages aren’t closed under $Perm(L)$

Problem Detail: 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.

Asked By : Elimination

Answered By : Yuval Filmus

Hints:

  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^*$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42752  Ask a Question  Download Related Notes/Documents