1
$\begingroup$

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.

$\endgroup$
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$ Mar 11 at 12:33
  • $\begingroup$ There is no order within a set. $\endgroup$
    – greybeard
    Mar 11 at 13:29
  • 1
    $\begingroup$ @Anonymous please edit the question to include what sort means instead of describing it in a comment $\endgroup$
    – Russel
    Mar 11 at 13:47
  • $\begingroup$ @Russel. I reformulated my question. $\endgroup$
    – Anonymous
    Mar 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$ Mar 12 at 1:41

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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