Informatiker Board | formale Sprachen | Operation auf Menge unklar

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Operation auf Menge unklar » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 10 Beiträge

dx_maniac_dx

Hallo

Ja, stimmt. Es steht überall und jetzt wie du es auch erwähnt hast.

Man sieht des öfteren folgendes:

Die Schreibweise für das kartesische Produkt zwischen den Mengen A und B ist $[latex]A \times B[/latex]$

oder

Das kartesische Produkt $[latex]A \times B[/latex]$ ..... .

Verstanden! Daumen hoch

und zum 2. muss ich sagen, dass ich mich falsch ausgedrückt habe großes Grinsen

Wie du es schon sagtest geht es um die Verkettung von 2 Wörtern zu einem neuen Wort und nicht Elementen.

Verstanden! Daumen hoch

So, jetzt hab ich es doch zu 100% verstanden großes Grinsen

Gruß

Erdem

Karlito

Hallo Erdem,

Ich muss dich enttäuschen, das ist es noch nicht ganz.

Zitat:

Original von dx_maniac_dx
$[latex]_{\sum}* _{\times}[/latex]$ $[latex]_{\sum}*[/latex]$ ergibt ein kartesisches Produkt: $[latex]_{\sum}*[/latex]$

Nein, $[latex]_{\sum}* _{\times}[/latex]$ $[latex]_{\sum}*[/latex]$ ist das Kartesische Produkt. Analog noch einmal: $[latex] \vec v \in \mathbb{R} \times \mathbb{R}[/latex]$

Die Operation $[latex]\circ[/latex]$ beschreibt nun, wie man aus einem solchen Paar, welches Element der Menge $[latex] \Sigma^* \times \Sigma^* [/latex]$ ist, ein neues Wort bildet. Nämlich durch aneinanderhängen. Das Ergebnis ist dann ein Element der Menge $[latex]\Sigma^*[/latex]$ .

Zitat:

Original von dx_maniac_dx
Es geht hierbei als nur um reine Verkettung von Elementen über Alphabeten zu neuen Wörtern, richtig?

Wie oben beschrieben stimmt das nicht ganz. Einfach gesagt geht es um die Verkettung von 2 Wörtern zu einem neuen.

Z.B. $[latex] \underbrace{aaaba}_{\in \Sigma^*} \circ \underbrace{abba}_{\in \Sigma^*} = \underbrace{aaabaabba}_{\in \Sigma^*} [/latex]$

VG,

Karlito

dx_maniac_dx

Hallo

ich habe mir erst mal weider den Satz im Buch es öfteren angeschaut und dein letzten Beitrag gelesen der mich um glaub ich zu 100% aufgeklärt hat.

Das war der entscheidende Satz:

Zitat:

Original von Karlito
Nein, das ist kein Plathalter für eine Operation. Es beschreibt eine Menge, bei der jedes Element einer Menge mit jedem Element einer anderen Menge kombiniert werden kann. Siehe Kartesisches Produkt.

Vor allem waren die Wörter jedes mit jedem und kombinieren sehr aufschlussreich.

Ich habe weiterhin im Zusammenhang mit deinen Beiträgen viele Informationen gesucht und bin zu diesem Schluss gekommen:

$[latex]_{\sum}* _{\times}[/latex]$ $[latex]_{\sum}*[/latex]$ ergibt ein kartesisches Produkt: $[latex]_{\sum}*[/latex]$

und dieses kartesische Produkt ist das Ergebnis von zwei Mengen, dessen Elemente zu einem geordnetem Paar zusammengefasst wurde. Das ist alles. Es werden lediglich Elemente zu einem geordnetem Paar zusammengefasst.

Wie du es schon erwähnt hast wird im Buch die stelle sehr verwirrend erklärt.

Ich frag mich nur warum der Autor nicht einfach ( $[latex]_{\sum}*[/latex]$ , o) oder umgekehrt $[latex]_{\sum}[/latex]$ + $[latex]_{\times}[/latex]$ $[latex] _{\sum}[/latex]$ + $[latex]\to[/latex]$ $[latex]_{\sum}[/latex]$ + an der stelle geschrieben hat anstatt so verwirrende.... ich sag mal Satzkonstruktion XD

Es geht hierbei als nur um reine Verkettung von Elementen über Alphabeten zu neuen Wörtern, richtig?

Gruß

Erdem

Karlito

Hallo,

zu 1.
Nein, das $[latex]\times[/latex]$ ist kein Plathalter für eine Operation. Es beschreibt eine Menge, bei der jedes Element einer Menge mit jedem Element einer anderen Menge kombiniert werden kann. Siehe Kartesisches Produkt.

So ist jeder 2-Dimensionale reelle Vektor ein Element der Menge $[latex]\mathbb{R} \times \mathbb{R}[/latex]$ bzw $[latex]\mathbb{R}^2[/latex]$ , da in einem Vektor jedes Element x aus den reellen Zahlen mit jedem Element y aus den reellen Zahlen kombiniert werden kann.

zu 2.
$[latex]\circ[/latex]$ beschreibt in der Mathematik oft eine Operation. Ungleich + oder * oder - wird bei dieser Operation oft noch definiert, was sie tut.

$[latex]\left(\Sigma^+, \circ\right)[/latex]$ beschreibt hierbei nur, dass die Operation $[latex]\circ[/latex]$ auf der Menge $[latex]\Sigma^+[/latex]$ definiert ist. Weiterhin wird textuell gesagt, dass $[latex]\left(\Sigma^+, \circ\right)[/latex]$ eine Halbgruppe bildet. Sowas wie $[latex] \circ \left(\Sigma^+,\circ \right)[/latex]$ ist also nicht richtig. Richtiger wäre sowas wie $[latex] \circ \left(x,y \right) [/latex]$ , wobei $[latex] x \in \Sigma^+[/latex]$ , $[latex] y \in \Sigma^+[/latex]$ und $[latex] \circ [/latex]$ ist die Konkatenationsfunktion.

Sicher verwirrend ist hier noch, dass die Operation und die Halbgruppe auf $[latex] \Sigma^+ [/latex]$ erklärt wird, die Abbildung jedoch auf $[latex] \Sigma^* [/latex]$ . Da jedoch $[latex] \Sigma^+ \subset \Sigma^* [/latex]$ ist, stimmt die Abbildung...

Ich hoffe noch etwas mehr Licht ins Dunkel gebracht haben zu können.

Gruß,

Karlito

dx_maniac_dx

Mir ist etwas aufgefallen.

Wir haben die allgemeine Form in zwei unterschiedlichen Situationen betrachtet.

Einmal, bei dem Beispiel den du erläutert hast:

Zitat:

Original von Karlito
Hallo,

es handelt sich um eine Abbildung aus der Menge des Kreuzproduktes aller Wörter über $[latex]\Sigma[/latex]$ in die Menge aller Wörter über $[latex]\Sigma[/latex]$ .

Wie diese Abbildung genau aussieht, darüber ist nichts gesagt.

Eine analogie zu dieser Abbildung (um zu Verstehen was sie bedeutet) ist z.B. die Betragsfunktion von Vektoren.

Gegeben ein Vektor $[latex]\vec v = \left(\begin{array}{c} x \\ y \end{array}\right)[/latex]$ , wobei $[latex] x \in \mathbb{R}[/latex]$ und $[latex] y \in \mathbb{R}[/latex]$ , so ist der Betrag des Vektors definiert durch $[latex]\left| \vec v \right| = \sqrt{x^2+y^2} [/latex]$ eine Abbildung der Form $[latex] \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R}[/latex]$ .

Für einen 3-Dimensionalen Vektor ist es entsprechend eine Abbildung der Form $[latex] \mathbb{R} \times \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R}[/latex]$ . oder auch kurz $[latex] \mathbb{R}^3 \mapsto \mathbb{R} [/latex]$

und dann bei meinem Beispiel:

Zitat:

Original von dx_maniac_dx
Hallo smile

1. Versteh ich jetzt richtig, dass das "x" (Kreuzprodukt) ein "Platzhalter" für Operatoren ist?

und

2. Das, wie du es beschrieben hast, die Konkatenation eine Funktion ist deren Name "o" lautet und somit gilt "o" gleichzeitig als Funktionsaufruf das folgendermaßen definiert ist: o( $[latex]\sum^{+}, o[/latex]$ ) und gibt anschließend wie im BUch ein Gruppenelement aus?

Dann nimmt die Funktion "o" (Konkatenation) zwei Parameter an: der erste Parameter sei ein Alphabet ohne das leere Wort ( $[latex]\sum^{+}[/latex]$ ) aber dann nimmt das zweite Parameter sich selber auf?

Gruß

Erdem

EDIT: Ich glaub ich schmeiße da vieles durcheinander.... das zweite Punkt ist glaub ich völliger Schwachsinn meiner seits....zweiten Punkt nicht beachten ^^

Karlito

Hallo,

ja, $[latex]\Sigma^* \times \Sigma^* \to \Sigma^*[/latex]$ beschreibt allgemein, was die Konkatenation macht. Eben eine Abbildung wie oben beschrieben.

Wirklich gerechnet wird da im herkömmlichen Sinne nichts, aber die Konkatenation ist halt ein Operator, ähnlich wie Plus und Minus. Nur dass hier halt bestimmte Eigenschaften nicht gelten. Die Konkatenation ist z.B. nicht Kommutativ und es gibt keine Umkehroperation (Element mit inversem gibt neutrales Element).

Kommutativität, Assoziativität und noch einige andere Eigenschaften sind Eigenschaften mathematischer Strukturen. Du wirst in Mathematik noch die Gruppentheorie kennenlernen. Da wird beschrieben wie das alles Funktioniert und welche Eigenschaften gelten müssen.

Die aussage mit der Rechenstruktur ist hier halt nur, dass die Konkatenation eine Funktion ist, welche 2 Parameter entgegennimmt und ein Ergebnis liefert. Und alles befindet sich im Raum aller Wörter über $[latex]\Sigma[/latex]$ ... Mehr nicht.

Ich denke wenn ihr die Gruppentheorie behandelt wird dir das klarer. Ich müsste jetzt einen langen Text schreiben um genauer auf die Eigenschaften anderer Gruppen einzugehen und was das von Halbgruppen unterscheidet. Frag am besten mal den Dozenten, wie tief das verständnis dessen gehen soll.

VG,

Karlito

dx_maniac_dx

Hallo

Also was assoziativ heißt ist mir klar zum glück ^^

Hmmm bin noch bisschen ziemlich unsicher...

Ist das:

$[latex]\sum^{*} X \sum^{*} \to \sum^{*}[/latex]$

die allgemein Form von dem:

v o w = vw ?

Und wird gesagt das ( $[latex]\sum^{+},[/latex]$ o) eine rechenstruktur ist und die Halbgruppe bildet?

Wenn ja, was ist denn daran eine Rechenstruktur?

Da wird doch nichts gerechnet....

Da wird ein Alphabet und ein Operator einfach nur in Klammern gesetzt.

Gruß

Erdem

Karlito

Halbgruppen sind mathematische Strukturen für die 2 Eigenschaften gelten:
1. Abgeschlossenheit
2. Assoziativität

Mehr sagt der 2. Absatz eigentlich auch nicht.

Abgeschliossenheit heißt, dass man mit der Operation auf die Gruppenelemente die Gruppe nicht verlässt. D.h. man erhält nur wieder ein Gruppenelement. Hier in dem Fall wieder ein Element von $[latex]\Sigma^*[/latex]$ . Und Assoziativität kennst du ja. Es ist egal, ob ich die Operation erst auf u und v anwende und danach noch mal an das Ergebnis von $[latex]u \circ v[/latex]$ noch einmal was hintendrankonkateniere oder die Konkatenation auf u und das "Produkt" von $[latex]v \circ w[/latex]$ anwende.

Die Assoziation ist vlt ein wenig missverständlich geschrieben, aber ich hoffe du weist was ich meine.

VG,

Karlito

dx_maniac_dx

Hmmm also gut der Operator X liefert den Kreuzprodukt und den Pfeil kann ich also einfach als Gleichheitszeichen sehen, richtig?

Hier ein Ausschnitt aus dem Buch mit dem Satz, dass mir Probleme macht bzw. ich nicht verstehe:

Mit $[latex]\sum^{+}[/latex]$ bezeichnen wir die Menge aller Wörter über $[latex]\sum[/latex]$ ohne das leere Wort, d.h.
$[latex]\sum^{+} = \sum^{*}[/latex]$ - { [latex]e[/latex]

}.

Im algebraischen Sinne bildet die Rechenstruktur ( $[latex]\sum^{+}[/latex]$ , o) für ein Alphabet $[latex]\sum[/latex]$ und die (Konkatenations-) Operation o : $[latex]\sum^{*} x \sum^{*} \to \sum^{*}[/latex]$ definiert durch v o w = vw eine Halbgruppe, denn die Konkatenation ist eine assoziative Operation: für alle Wörter u, v, w $[latex]\in \sum^{*}[/latex]$ gilt u o (v o w) = (u o v) o w.

So der erste Teil ist mir völlig klar ich habe es nur noch mit reingeschrieben vllt weil es ein zusammenhang mit dem nächsten problematischen Teil hat den ich nicht verstehe. Dieser 2. Abschnitt haut mich einfach um. Ich habs über 10mal gelesen und noch immer nicht verstanden. ALso ab "Im algebraischen SInne...."

Hoffe Ihr könnt mich aufklären.

Gruß

Erdem

Karlito

Vielen Dank für den Hinweis... Wusste ich so nicht.

Gruß,

Karlito

Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen.