Problem Detail: Assume $L$ is a regular language over an ordered alphabet. Is the language built by taking every word in $L$ and sorting it always a regular language?
Asked By : Andrew MacFie
Answered By : Niel de Beaudrap
No. Counterexample: assuming $a < b$, we have $(ab)^ast xrightarrow{;;text{sorted};;} { a^n b^n ;|; n geqslant 0 }$, which cannot be expressed by a regular expression, by the pumping lemma for regular languages.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2861
