Definition - Lexikographische Totalordnung

• Generalisierungen:
  • Totalordnung
• Involvierte Definitionen:
  • Totalordnung
  • Alphabet
  • Wort
  • Menge aller Wörter
• Veranstaltung: AlMa
• Referenz: } AlgoMathe KE2 - Partialordnungen

⠀

Definition: Lexikographische Totalordnung

Sei ein Alphabet.
Sei die Menge aller Wörter mit beliebiger Länge.

Seien beliebige Wörter, dann definieren wir die lexikographische Ordnung wie folgt:

Anmerkung

Interpretation

Das heißt, gilt genau dann, wenn:

• .
  und mit den gleichen Buchstaben anfangen (wobei auch sein kann, die Wörter also gar keine Überschneidung haben)
• .
  Nach den ersten Buchstaben ein Buchstabe kommt, für den gilt:
• .
  Oder nach den ersten Buchstaben schon zu Ende ist.

Beispielhafte Belegungen

Beispielsweise so:

Die gewohnte Ordnung wäre:

Dann wäre ein Wort beispielsweise “aanfg”: