Closure of regular languages under permutation 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.
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).