Wie bestimme ich die lexikographische- bzw Standardordnung?
Gegeben seien das Alphabet Σ , { a, b, c } und die totalen Ordnungen R2 : (Σ, Σ) mit R2:= { (a, a), (a, c), (b, a), (b, b), (b, c), (c, c) }.
Aufgabe:
Ordne die Wörter λ, c, cc, ccc, ca, abc, bac nach der lexikographischer und Standardordnung bzgl. R2.
Es gibt dazu Lösungen, nur weiß ich nicht wie ich darauf kommen soll
Lösungen:
lexikographische Ordnung:
λ << bac << abc << c << ca << cc << ccc
Standardordnung:
λ << c << ca << cc << bac << abc << ccc
2 Antworten
Ok, ich musste mich da auch jetzt erstmal reindenken, aber ich glaub ich hab es langsam. Auch wenn das jetzt nur meine Ideen sind und ich dir nicht alles wasserdicht belegen kann.
Durch (b, a), (b, c), (a, c) (d.h. "b vor a", "b vor c", "a vor c") hab ich ja die Abfolge b<a<c als Reihenfolge zum Ordnen.
Bei der Standardordnung geht es wohl als erstes nach der Länge der Wörter (also z.B. zuerst alle Wörter der Länge 2, bevor das erste Wort der Länge 3 kommt) und die Wörter gleicher Länge werden dann untereinander nach dieser Reihenfolge sortiert.
Deshalb kommt erst das leere Wort, dann c als Wort der Länge 1, dann ca vor cc als Wörter der Länge 2 (da erster Buchstabe gleich und a vor c im zweiten Zeichen) und als Wörter der Länge 3 bac << abc << ccc (da hier nach obiger Reihenfolge nach dem ersten Buchstaben sortiert wird).
Die lexikographische Ordnung sortiert wohl ungeachtet nach der Wortlänge erstmal ausgehend vom ersten Buchstaben nach obiger Regel:
λ
bac
abc
c << ca << cc << ccc
Dann werden die mit Anfangsbuchstaben c nach dem zweiten Buchstaben sortiert:
c
ca
cc << ccc
Hier bleiben cc und ccc übrig, da beide an zweiter Stelle ein c haben.
Und im letzten Schritt dann
cc
ccc
In beiden Fällen müsste es:
abc << bac
und nicht
bac << abc
lauten.
Die Lexikografische Sortierung ist die aus dem Telefonbuch, Duden, etc. Also das, was für uns natürlich ist. Die Wörter werden links ausgerichtet und dann sortiert.
Bei der Standardsortierung wird erst nach der Länge sortiert und gleich lange dann lexikografisch. Bzw. die Worte werden nach rechts ausgerichtet und dann lexikografisch sortiert.
Da ich mir ja oben meine eigene Sortierreihenfolge in den Regeln definiert habe, in denen eben b vor a kommt, hab ich hier eben grade NICHT die Standardsortierung.