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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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