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.
5
-
1$\begingroup$ 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? $\endgroup$– Narek BojikianMar 11 at 12:33
-
$\begingroup$ There is no order within a set. $\endgroup$– greybeardMar 11 at 13:29
-
1$\begingroup$ @Anonymous please edit the question to include what sort means instead of describing it in a comment $\endgroup$– RusselMar 11 at 13:47
-
$\begingroup$ @Russel. I reformulated my question. $\endgroup$– AnonymousMar 11 at 13:54
-
1$\begingroup$ 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 \}$. $\endgroup$– Hendrik JanMar 12 at 1:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Mar 11 at 14:07