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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
answered Jul 23 '12 at 0:07