[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