2
$\begingroup$

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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
6
$\begingroup$

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^*$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ And also $Perm((012)^*) \cap 0^*1^*2^*$, which jumps from regular ouside context-free. $\endgroup$
    – Hendrik Jan
    Commented May 19, 2015 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.