Informatiker Board | formale Sprachen | Operation auf Menge unklar

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

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Operation auf Menge unklar

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

dx_maniac_dx
Grünschnabel

Dabei seit: 26.01.2012
Beiträge: 6

Operation auf Menge unklar

Zitatantwort auf diesen Beitrag erstellen

Hallo,

ich habe ein Verständnis Problem über.... Wortbildungen? Ich weiß es nicht.

Ich hab mir ein Buch gekauft über Theoretische Informatik und verstehe folgendes nicht:

£* x £* -> £*

Ist das eine Definition, Aussage oder eine Bildung von etwas?

Um genauer zu sein es geht mir hier dabei um die operation X und um das -> Zeichen.

Was bedeuten die? Ich habe im Buch nichts gefunden komischerweiße... -.- und hab im internet auch viel gesucht aber nichts gefunden...

Ich hoffe ihr könnt mir helfen

Gruß

Erdem

PS: Die komischen Pound zeichen sollen Sigma sein

26.01.2012 02:53

Nehmen Sie dx_maniac_dx in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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]$

Ich hoffe das macht es deutlich.

VG,

Karlito

26.01.2012 22:25

Nehmen Sie Karlito in Ihre Freundesliste auf

matheMensch
unregistriert

Zitat:

Original von Karlito
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]$ .

Wenn man Abbildungen definiert benutzt man allerdings den einfachen Pfeil $[latex]\to[/latex]$ und nicht $[latex]\mapsto[/latex]$ .
Diesen benutzt man, wenn man die Abbildungsvorschrift definiert. Hier als Beispiel für die 2-norm:

$[latex]|\cdot| : \mathbb{R}^2\to\mathbb{R}, \begin{pmatrix}x\\y\end{pmatrix}\mapsto \sqrt{x^2+y^2}[/latex]$

28.01.2012 12:12

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Gruß,

Karlito

28.01.2012 13:12

dx_maniac_dx
Grünschnabel

Dabei seit: 26.01.2012
Beiträge: 6

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

29.01.2012 18:28

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 29.01.2012 22:45.

29.01.2012 22:42

dx_maniac_dx
Grünschnabel

Dabei seit: 26.01.2012
Beiträge: 6

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

30.01.2012 13:10

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

30.01.2012 15:02

dx_maniac_dx
Grünschnabel

Dabei seit: 26.01.2012
Beiträge: 6

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 ^^

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dx_maniac_dx: 30.01.2012 16:46.

30.01.2012 16:25

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von Karlito: 01.02.2012 10:43.

31.01.2012 22:29

dx_maniac_dx
Grünschnabel

Dabei seit: 26.01.2012
Beiträge: 6

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

01.02.2012 20:38

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

01.02.2012 21:17

dx_maniac_dx
Grünschnabel

Dabei seit: 26.01.2012
Beiträge: 6

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

02.02.2012 19:56

Baumstruktur | Brettstruktur

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