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:
- For regular languages, consider $Perm((01)^*) cap 0^* 1^*$.
- 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