Lexikogr. Ordnung < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | 0,01,11,001,010,011,0001.0101
sollen lexikographisch geordnet werden, wobei 0 > 1 für jedes Bit gilt |
So, die Lösung ist:
0 < 0001 < 001 < 01 < 010 < 0101 < 011 < 11.
Wieso?
Ich dachte, bei einer lexikographische Ordnung kommt es zuerst auf die Länge an und bei gleicher Länge schaut man sich die einzelnen Bestandteile (hier die Bits) an.
Ich hätte das so gelassen, wie es in der Aufgabenstellung schon ist.
Laut meinem Buch über theoret. Informatik ist zum Beispiel bei der lexikogr. Ordnung des Alphabets {a,b} das Wort bb < aaa
|
|
| |
|
Hallo,
> 0,01,11,001,010,011,0001.0101
>
> sollen lexikographisch geordnet werden, wobei 0 > 1 für
> jedes Bit gilt
> So, die Lösung ist:
>
> 0 < 0001 < 001 < 01 < 010 < 0101 < 011 < 11.
>
> Wieso?
>
> Ich dachte, bei einer lexikographische Ordnung kommt es
> zuerst auf die Länge an und bei gleicher Länge schaut man
> sich die einzelnen Bestandteile (hier die Bits) an.
Wie ist denn eure genaue Definition von lexikographischer Ordnung?
Die Lösung entspricht der Definition von lexikographischer Ordnung, wie sie auf wikipedia steht ...
>
> Ich hätte das so gelassen, wie es in der Aufgabenstellung
> schon ist.
>
> Laut meinem Buch über theoret. Informatik ist zum Beispiel
> bei der lexikogr. Ordnung des Alphabets {a,b} das Wort bb < aaa
Das passt m.E. nicht zu der Definition auf wikipedia ...
Gruß
schachuzipus
|
|
|
| |
|
Lexikographische Ordnung auf [mm] \summe [/mm] * x [mm] \summe [/mm] * (soll das Kreuzprodukt des Kleene-Abschlusses von Sigma sein)
Seien v = [mm] v_{1}, v_{2}, [/mm] ... [mm] v_{m}, v_{i} \in \summe_ [/mm] , 1 [mm] \le [/mm] i [mm] \le [/mm] m und w = [mm] w_{1}, w_{2}, [/mm] ... [mm] w_{n}, w_{j} \in \summe [/mm] , j [mm] \le [/mm] 1 [mm] \le [/mm] n , dann ist v vor w genau dann, wenn
m < n
n = m und es ein k, 1 [mm] \le [/mm] k < m gibt, sodass v1, ... vk = w1, ... , wk sowie [mm] v_{k+1} [/mm] < [mm] w_{k+1}
[/mm]
Hoffe, ich habe es richtig abgetippt.
Und laut dem Buch hier bedeutet [mm] \summe [/mm] = {a, b} auch, dass a < b ist... was mir etwas komisch vorkommt.
|
|
|
|
