HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

Are regular languages closed under sort (Parikh image)?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
imagearelanguagesparikhregularclosedundersort

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#2861, answer score: 17

Revisions (0)

No revisions yet.