Assoziat.der Konkatenation < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe 1 | Zeigen Sie, dass die Konkatenation von Wörtern eine assoziative Operation auf
[mm] \mathcal{A} [/mm] * mit [mm] \varepsilon [/mm] als neutralem Element ist. Ist sie kommutativ? ( [mm] \mathcal{A} [/mm] * ist die Summe aller Wörter über dem Alphabet) |
| Aufgabe 2 | Zeigen Sie, dass die Konkatenation von Sprachen eine assoziative Operation auf
[mm] P(\mathcal{A} [/mm] *) ist. Geben Sie ein neutrales Element an. (Potenzmenge) |
Hi ihr,
ich hab leider wenig Ahnung von mathematischen Beweisen, daher poste ich die Frage hier.
Ansatz:
Frage 1:
a, b, c [mm] \varepsilon \mathcal{A} [/mm] *
z.z.: (a b) c <=> a (b c)
Wie soll man etwas offensichtliches Beweisen???
Das das ganze Assoziativ sein soll über [mm] \mathcal{A} [/mm] * heißt vermutlich, dass das entstehende Wort in [mm] \mathcal{A} [/mm] * liegen soll.
Frage 2:
Jetzt hörts spätenstens ganz auf bei mir.
Wie kann man Sprachen miteinander konkatenieren?
Und das entstehende Wort soll dann wohl wieder in der Potenzmenge liegen?
Bitte, helft einem Informatiker, der von Mathe kaum Ahnung hat ;D
P.S.:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Tag,
also zunächst ist es doch so, daß Ihr sicherlich in der Lehrveranstaltung mal eine Def. der Konkatenation bekommen habt, und daran sollte man sich
dann bei den Aufgaben auch orientieren.
Man könnte zB definieren:
[mm] \epsilon [/mm] x = [mm] x\epsilon [/mm] =x [mm] ,\:\: x\in A^{\star}
[/mm]
und
[mm] (x_1\ldots x_n) (y_1\ldots y_m) [/mm] = [mm] z_1\ldots z_{m+n} [/mm]
mit [mm] z_j=x_j,\: 1\leq j\leq n,\quad z_j=y_{j-n},\: n+1\leq j\leq [/mm] m
und dann die Assoziativität aus dieser Definition beweisen.
Es ist übrigens sicherlich [mm] A^{\star} [/mm] die Menge aller endlichen Strings über A (und nicht die Summe).
Dann kann man zB für [mm] X,Y\subseteq A^{\star}
[/mm]
[mm] XY:=\{xy\: |\: x\in X, y\in Y\}
[/mm]
setzen.
Dann ist doch die Menge [mm] \{\epsilon\} [/mm] (die nur den leeren String enthält) das neutrale Element für die
Konkatenation von Sprachen.
Gruss,
Mathias
ps. Wenn Du also noch Hilfe brauchst: Schreib bitte dann in die Nachfrage Eure Definitionen mit hinein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:42 Di 02.05.2006 | | Autor: | dobberph |
Hi,
zu Aufgabe 1 habe ich eine Lösung,
aber zur 2. Aufgabe weiß ich nach wie vor nicht genau, was ich machen muss.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:24 Di 02.05.2006 | | Autor: | dobberph |
Bekannte Definitionen:
|w| bezeichnet die Länge des Wortes w
über jedem Alphabet gibt es das leere Wort ε mit |ε|=0
Σ* bezeichnet die Menge aller Wörter über Σ
◦ : Σ* x Σ* Σ* mit u◦v := uv Aneinanderfügen von Wörtern
assoziative Operation mit ε als neutralem Element
(Σ*,◦,ε) bildet ein Monoid
statt u◦v scheibt man meist uv
Σ0 := {ε}
Σn+1 := {wa | wєΣn, aєΣ}
Σ+ := Un≥1 Σn
|
|
|
| |
|
Hallo nochmal,
ok, prima, wenn Du die erste Aufgabe schon hast.
Dann ist doch für [mm] X,Y\subseteq A^{\star} [/mm] definiert:
[mm] XY=\{xy|x\in X, y\in Y\} [/mm]
ZZg: X(YZ)=(XY)Z [mm] \:\:\: (X,Y,Z\subseteq A^{\star})
[/mm]
Aber laut obiger Def. ist dann doch zu zeigen:
[mm] X(YZ)=\{xc|x\in X, c\in YZ\} \:\: =\:\: \{az|a\in XY, z\in Z\}
[/mm]
Wieder Def. von YZ (linke Seite) und XY (rechte Seite) einsetzen, und dann steht es schon da.
Gruss + viel Erfolg,
Mathias
ps. Falls Deine Angaben zur Konkatenation vollständig waren, ist das allerdings ein wenig dürftig.
Ohne essentiellen Mehraufwand kann man die formale Def. liefern, und dann weiss jede(r) auch, was man
im Detail zeigen muss.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:03 Di 02.05.2006 | | Autor: | dobberph |
Hi,
das Problem bei der 2. Aufgabe ist für mich, dass es hier nicht mehr um Wörter handelt, sonder um eine Konkatenation von Sprachen.
Ist es das, was du aufgeschrieben hast? Oder ist es dann was anderes?
Das ist für mich nämlich das Verständnisproblem...
Mfg,
DerTobi
|
|
|
| |
|
Hallo DerTobi!
> das Problem bei der 2. Aufgabe ist für mich, dass es hier
> nicht mehr um Wörter handelt, sonder um eine Konkatenation
> von Sprachen.
> Ist es das, was du aufgeschrieben hast? Oder ist es dann
> was anderes?
Ja, Mathias hat genau das aufgeschrieben. Was ist denn überhaupt eine "Sprache"? Im Prinzip ist das doch nur eine Menge von Wörtern, oder? (ohoh - hoffentlich mache ich jetzt nichts falsch, sonst bekomme ich später noch eins auf den Deckel... ![[bonk]](/images/smileys/bonk.gif "[bonk]") ) Und was war [mm] A^{\star}? [/mm] Das war doch die Menge aller endlichen Strings über A, wie Mathias schon vorher erwähnt hatte. Was ist dann [mm] $X\subseteq A^{\star}$? [/mm] Eine Teilmenge aller (endlichen) Wörter, also wiederum eine "Menge von Wörtern" (oder heißt es "Worten"?  ) und somit auch eine Sprache.
Und was bedeutet: $ [mm] XY:=\{xy\: |\: x\in X, y\in Y\} [/mm] $? Das bedeutet folgendes:
Wenn ich die Sprache Y an die Sprache X hänge, also beide Sprachen konkateniere (X und Y sind ja [mm] $\subseteq A^{\star}$, [/mm] also Sprachen), dann ist das definiert als "Menge aller Wörter xy", wobei gilt, dass das (Teil-)Wort x in der Sprache X liegt und das (Teil-)Wort y in der Sprache Y. Somit ist dann die Konkatenation die Menge aller Wörter, die ich bilden kann, wenn ich zuerst (irgend) ein Wort aus X nehme und dann (irgend) eins aus Y. Evtl. hilft dir auch ![[]](/images/popup.gif) der Wiki-Artikel über Formale Sprachen.
> Das ist für mich nämlich das Verständnisproblem...
Jetzt etwas klarer? Ansonsten versuch nochmal, genau dein Problem zu formulieren. Eigentlich ist das nämlich gar nicht so schwierig, sofern man die Mengenoperationen genau liest.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:32 Di 02.05.2006 | | Autor: | dobberph |
Hi,
eigentlich hab ichs jetzt schon verstanden, aber damit ist Frage 2 nicht wirklich beantwortet oder?
Man soll ja die Assoziativität auf der Potenzmenge zeigen und das neutrale Element angeben ... ?!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 04.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
