# Transform a non-regular language into a regular one using sort

Is there a way where sort turns a non regular language into a regular one. What I mean by sort is this: Consider the language $$L =$$ { $$bac, cbca, acbb$$}. $$sort(L) =$$ {$$abc, abcc, abbc$$} respectively. If there is, do you have an example. If not can you provide a proof if you can.

• Can you define the operator in more precise terms, do you mean writing all zeroes before ones and writing all as before bs before cs etc? Commented Mar 11, 2023 at 12:33
• There is no order within a set. Commented Mar 11, 2023 at 13:29
• @Anonymous please edit the question to include what sort means instead of describing it in a comment Commented Mar 11, 2023 at 13:47
• @Russel. I reformulated my question. Commented Mar 11, 2023 at 13:54
• Sort may also do the opposite: changing a regular language into a nonregular one: from $(abc)^*$ into $\{a^nb^nc^n\mid n\ge 0 \}$. Commented Mar 12, 2023 at 1:41

## 1 Answer

No the class of all non-regular languages is not closed under sort. For example take the language $$L=\{a^nba^n\}$$. It is clearly not regular (by the pumping lemma). However, $$sort(L)$$ is the language defined by even many $$a$$s and then a $$b$$. This language is clearly regular.