1
$\begingroup$

Given a regular language $L$ over the alphabet $\Sigma = \{a,b,c,d\}$, is the language $\mathrm{Perm}(L)$ consisting of all permutations of words in $L$ also regular?

My intuition says it is, since each word in $L$ only has finitely many permutations, but I don't know how to prove it.

Any help would be great.

$\endgroup$
4
  • $\begingroup$ Are you asking whether this holds for every regular language? (it doesn't), or whether this is a decidable problem? $\endgroup$ – Shaull Apr 23 at 11:40
  • $\begingroup$ @Shaull - the first option - does this hold for every regular language. can you give an example for such L? $\endgroup$ – Galyoss Apr 23 at 11:43
  • 3
    $\begingroup$ try to think of languages that are not regular, but are closed under permutations. Hint: automata cannot "count". If you still can't find an example, detail some of your attempts in the post, and we'll help. $\endgroup$ – Shaull Apr 23 at 11:47
  • $\begingroup$ Got it. Thank you @Shaull ! $\endgroup$ – Galyoss Apr 23 at 11:49
6
$\begingroup$

You can consider the regular language $(ab)^*$. We have $$ \mathrm{Perm}((ab)^*) \cap a^*b^* = \{ a^n b^n : n \geq 0 \}, $$ which isn't regular. If you take instead $(abc)^*$ and intersect with $a^*b^*c^*$, you get the language $\{ a^nb^nc^n : n \geq 0 \}$, which isn't even context-free.

In contrast, the class of context-sensitive languages is closed under permutation. To see this, it suffices to observe that you can nondeterministically permute the input without any additional space (for example, by applying an arbitrary number of transpositions).

$\endgroup$
3
$\begingroup$

It is not regular.

Counter example:

Take $L= L((ab)^*)$. Now look at $Perm(L)$. It is the language of all words $w$ such that $|w|_a =|w|_b$.

Now, show that the pumping lemma doesn't apply.

Hint:

Take the word $a^Nb^N$ for $N$ the pumping length.

$\endgroup$

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