Sind reguläre Sprachen unter Sortierung geschlossen (Parikh-Bild)?

10

Angenommen, ist eine reguläre Sprache über einem geordneten Alphabet. Ist die Sprache aufgebaut, indem jedes Wort in L genommen und immer sortiert wird?LL

Andrew
quelle

Antworten:

17

Gegenbeispiel: Unter der Annahme von haben wir ( a b ) a<b , das nicht durch einen regulären Ausdruck ausgedrückt werden kann, durch dasPump-Lemma für reguläre Sprachen.(ab)sorted{anbn|n0}

Niel de Beaudrap
quelle