Partielle Ordnung < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:32 So 15.12.2013 | | Autor: | rsprsp |
| Aufgabe | Sie M die Menge aller Worte der Länge 1 bis 3 über dem Alphabet {x,y}. Welche der folgenden Relationen sind partielle Ordnungen?
1. (a,b) Element Relation1 genau dann, wenn a ein Präfix (d.h "Anfangskette") von b ist.
1. (a,b) Element Relation2 genau dann, wenn a ein Suffix (d.h "Endkette") von b ist.
1. (a,b) Element Relation1 genau dann, wenn a ein Präfix oder ein Suffix von b ist. |
Hallo, ich brauche Hilfe beim Ansatz dieser Aufgabe. Ich komme immer noch nicht wirklich drauf was ein Alphabet dieser Art ist und wie es aussieht.
Überlegt habe ich mir, dass es in dem Fall so aussehen könnte.
Es gibt 1 bis 3 Elemente und diese sind entweder x oder y. D.h gibt es diese Möglichkeiten:
{x,y,xy,yx,xx,yy,xxx,xxy,xyx,yxx,xyy,yxy,yyx,yyy}
und ich soll jetzt gucken welche davon jetzt partielle Ordnungen sind bzw noch auf Bedingung achten...
Liege ich damit richtig?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:03 So 15.12.2013 | | Autor: | Ebri |
> Hallo, ich brauche Hilfe beim Ansatz dieser Aufgabe. Ich
> komme immer noch nicht wirklich drauf was ein Alphabet
> dieser Art ist und wie es aussieht.
Hallo
Ein Alphabet [mm] (\Sigma) [/mm] ist eine endliche, nichtleere Menge. Die Elemente eines Alphabets nennt man Zeichen, Buchstaben oder Symbole.
Hier ist das Alphabet [mm] \Sigma [/mm] = {x,y}. Das Alphabet dient als Zeichenvorrat aus dem man Wörter bauen kann.
> Überlegt habe ich mir, dass es in dem Fall so aussehen
> könnte.
> Es gibt 1 bis 3 Elemente und diese sind entweder x oder y.
> D.h gibt es diese Möglichkeiten:
> {x,y,xy,yx,xx,yy,xxx,xxy,xyx,yxx,xyy,yxy,yyx,yyy}
"Sei M die Menge aller Wörter der Länge 1 bis 3 über dem Alphabet {x,y}." D.h. alle Wörter der Länge 1 bis 3 die man aus [mm] \Sigma [/mm] = {x,y} bauen kann.
M = {x,y,xy,yx,xx,yy,xxx,xxy,xyx,yxx,xyy,yxy,yyx,yyy} ![[ok]](/images/smileys/ok.gif "[ok]")
> und ich soll jetzt gucken welche davon jetzt partielle
> Ordnungen sind bzw noch auf Bedingung achten...
>
> Liege ich damit richtig?
Jetzt gilt es herauszufinden, welche der drei Relationen eine partielle Ordnung auf M bilden.
Welche Relation ist transitiv, reflexiv und antisymmetrisch auf M? Entweder ein Gegenbeispiel angeben, dass eine der drei Bedingungen für eine partielle Ordnung nicht erfüllt ist oder zeigen, dass alle drei erfüllt sind.
Ich hoffe ich konnte helfen.
Ebri
|
|
|
|
