# Closure of regular languages under permutation

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).