Gleichheit zweier Mengen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:02 So 07.07.2013 | | Autor: | bandchef |
| Aufgabe | Beweisen Sie folgende Aussage [mm] $(L_1 \cup L_2)^{\star} [/mm] = [mm] (L_1^{\star} \cdot L_2^{\star})^{\star}$
[/mm]
Zur Erläutering: Der [mm] \cdot [/mm] ist der Konkatenationsoperator und der [mm] \star [/mm] soll die Kleene'sche Hülle sein. Das alles geht auf Sprachen aber sind ja eigentlich auch alles nur Mengen, weshalb ich hier ins Mengenlehre Forum geschrieben habe. |
So, ich hab dann mal so angefangen:
Gleichheit von Mengen beweist man ja indem man erst eine Teilmenge von der einen Seite und eine Teilmenge von der anderen Seite betrachtet. Nach diesem Satz betrachtet $A=B [mm] \Leftrightarrow [/mm] (A [mm] \subseteq [/mm] B [mm] \wedge [/mm] B [mm] \subseteq [/mm] A)$ bekommt man also zwei Richtungen für die Betrachtung:
1. $A [mm] \subseteq [/mm] B$: [mm] $(L_1 \cup L_2)^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star} \subseteq [/mm] ...$
Weiter bin ich leider noch nicht gekommen. Das Problem ist nun die weitere Umformung. Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:15 Mo 08.07.2013 | | Autor: | Micha |
> Beweisen Sie folgende Aussage [mm](L_1 \cup L_2)^{\star} = (L_1^{\star} \cdot L_2^{\star})^{\star}[/mm]
> Gleichheit von Mengen beweist man ja indem man erst eine
> Teilmenge von der einen Seite und eine Teilmenge von der
> anderen Seite betrachtet. Nach diesem Satz betrachtet [mm]A=B \Leftrightarrow (A \subseteq B \wedge B \subseteq A)[/mm]
soweit so gut...
> bekommt man also zwei Richtungen für die Betrachtung:
>
>
> 1. [mm]A \subseteq B[/mm]: [mm](L_1 \cup L_2)^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star} \subseteq ...[/mm]
>
> Weiter bin ich leider noch nicht gekommen. Das Problem ist
> nun die weitere Umformung. Könnt ihr mir helfen?
Die Kette verstehe ich ehrlich gesagt nicht, da du hier ja die Eigenschaft, die du beweisen willst, schon benutzt.
Versuche es mal elementweise:
[mm]A \subseteq B \gdw ( \forall a \in A : a \in B )[/mm]
(und umgekehrt)
Ich bin mir aber nicht sicher, ob die Aussage wirklich gilt:
Nehmen wir [mm]L_1 = \{a\}[/mm] und [mm]L_2 = \{b\}[/mm]. Dann ist
[mm]L_1^\ast = \{e, a, aa, aaa, aaaa, \dots \}[/mm] und [mm]L_2^\ast = \{e, b, bb, bbb, bbbb, \dots \}[/mm].
Nun bilde ich die Vereinigung. Links habe ich:
[mm](L_1 \cup L_2)^\ast = \{e, a, b, ab, ba, aaa, aab, aba, baa,bab, bba, bbb, aaaa, aaab, \dots \}[/mm]
und rechts:
[mm](L_1^\ast * L_2^\ast)^\ast = \{e, a, b, ab,aaa, aab, abb, bbb, aaab, aabb, abbb, bbbb, \dots \}[/mm]
Ich habe die Wörter mal der Länge nach sortiert. Ich hoffe es wird klar, dass z.B. [mm]aba[/mm] nicht auf der rechten Seite vorkommt. Oder habe ich etwas übersehen?
Gruß Micha
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:03 Mi 10.07.2013 | | Autor: | bandchef |
Hallo Micha, danke für deine Antwort!
Ich kann deinen Ausführungen soweit folgen, aber was ich nicht verstehe ist, warum du $ [mm] L_1^\ast [/mm] = [mm] \{e, a, aa, aaa, aaaa, \dots \} [/mm] $ schreibst. Ich nehme mal an, dass du mit e das leere Wort [mm] $\epsilon$ [/mm] meinst. Meines Wissens nach, ist das Leere Wort nur dann in der Sprache, wenn man die Kleene'sche Hülle über [mm] $\Sigma$ [/mm] bildet...
Du schreibst "Versuche es mal elementweise:" und bildest unendliche Mengen von der du dir dann ein Element rauspickst. Soweit hab ich das verstanden. Das Element aba kommt auch in der rechten Menge (die mit der Konkatenation) nicht vor, SO LANGE die äußerste Kleene'sche Hülle noch nicht gebildet wurde! Da diese aber gebildet werden muss, kommt so auch aba in der rechten Meng vor und es sollte so die rechte und linke Menge gleich sein!
Was sagst du?
Aber, was mich an diesem "Beweis" etwas stört, weil es eben unendliche Mengen sind. Kann man dies nicht "allgemein zeigen"?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:07 Do 11.07.2013 | | Autor: | felixf |
Moin,
> Ich kann deinen Ausführungen soweit folgen, aber was ich
> nicht verstehe ist, warum du [mm]L_1^\ast = \{e, a, aa, aaa, aaaa, \dots \}[/mm]
> schreibst. Ich nehme mal an, dass du mit e das leere Wort
> [mm]\epsilon[/mm] meinst.
ja, das meint er wohl. Ein $e$ ist auch einfacher zu schreiben als [mm] $\epsilon$ [/mm] :)
> Meines Wissens nach, ist das Leere Wort
> nur dann in der Sprache, wenn man die Kleene'sche Hülle
> über [mm]\Sigma[/mm] bildet...
Du meinst [mm] $\Sigma^\ast$?
[/mm]
[mm] $\epsilon$ [/mm] ist das einzige Wort, was in der Kleene'schen Huelle jeder Sprache vorkommt.
> Aber, was mich an diesem "Beweis" etwas stört, weil es
> eben unendliche Mengen sind. Kann man dies nicht "allgemein
> zeigen"?
Welchen "Beweis" meinst du gerade?
Versuch es doch mal allgemein zu zeigen. Sei $w [mm] \in (L_1 \cup L_2)^\ast$. [/mm] Dann gibt es ein $n [mm] \in \IN$ [/mm] ($n = 0$ ist auch moeglich!) und [mm] $w_1, \dots, w_n \in L_1 \cup L_2$ [/mm] mit $w = [mm] w_1 \cdots w_n$.
[/mm]
Wenn du jetzt argumentierst, dass [mm] $w_i$ [/mm] auch in [mm] $L_1^\ast \cdot L_2^\ast$ [/mm] liegt, bekommst du so [mm] $(L_1 \cup L_2)^\ast \subseteq (L_1^\ast \cdot L_2^\ast)^\ast$ [/mm] gezeigt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:00 Do 11.07.2013 | | Autor: | bandchef |
Ich habe heute meinen Prof gefragt. Der meinte folgendes:
1.) [mm] $"\subseteq":$
[/mm]
[mm] $(L_1 \cup L_2)^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star} \subseteq((L_1^{\star} \cdot L_2^{\star}) \cup (L_2^{\star} \cdot L_1^{\star}))^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star}$
[/mm]
Diese Kette mit Erläuterungen würden ihm reichen. Denn, bei erster Menge auf die zweite Menge wird die Menge vergrößert, was die Inklusion ja erlaubt. Von zweiter Menge auf die dritte Menge, wird die Menge durch das konkatenierte L2* und L1* auch nur größer. Danach wird nur noch die Vereinigung auf die jeweils beiden konkatenierten Mengen angewendet und die Vereinigung mache die Menge auch nur größer. Danach ist man aber dann bei der Form wie bei Aussage 2 auf der rechten Seite gefordert wird!
Er meinte dann: Die Rückrichtung, also das Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
bekäme ich sicher selber hin. Und jetzt bin ich wieder genau da, wo ich vor ein paar Tagen hier eigentlich gefragt hatte; nämlich bei:
2.) $"\supseteq"$:
Also muss ich hier jetzt irgendwie sowas zeigen wie $(L_1^{\star} \cdot L_2^{\star})^{\star} \subseteq (L_1 \cup L_2}^{\star})$...
> Versuch es doch mal allgemein zu zeigen. Sei $w \in (L_1 \cup L_2)^\ast$. Dann gibt es ein $n \in \IN$ ($n = 0$ ist auch >moeglich!)
> und $w_1, \dots, w_n \in L_1 \cup L_2$ mit $w = w_1 \cdots w_n$.
> Wenn du jetzt argumentierst, dass $w_i$ auch in $L_1^\ast \cdot L_2^\ast$ liegt,
> bekommst du so $(L_1 \cup L_2)^\ast \subseteq (L_1^\ast \cdot L_2^\ast)^\ast$ gezeigt.
Kann man das jetzt nicht auch auf die "Rückrichtung" anwenden? Denn du hast das ja jetzt für die Richtung gemacht, für die ich die Lösung vom Prof. bekommen hab...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:34 Fr 12.07.2013 | | Autor: | felixf |
Moin!
> Ich habe heute meinen Prof gefragt. Der meinte folgendes:
>
> 1.) [mm]"\subseteq":[/mm]
>
> [mm](L_1 \cup L_2)^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star} \subseteq((L_1^{\star} \cdot L_2^{\star}) \cup (L_2^{\star} \cdot L_1^{\star}))^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star}[/mm]
Ich glaube nicht dass der das gesagt hat, ansonsten haettest du ja auch gleich nur [mm] $(L_1 \cup L_2)^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star}$ [/mm] schreiben brauchen, bis zur ersten Inklusion, da das schon das ist was du zum Schluss haben willst.
Kann es sein, dass es [mm](L_1 \cup L_2)^{\star} \subseteq (L_1^{\star} \cup L_2^{\star})^{\star} \subseteq((L_1^{\star} \cdot L_2^{\star}) \cup (L_2^{\star} \cdot L_1^{\star}))^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star}[/mm] lauten sollte?
> Diese Kette mit Erläuterungen würden ihm reichen. Denn,
> bei erster Menge auf die zweite Menge wird die Menge
> vergrößert,
Sie wird nicht vergroessert (schliesslich gilt ja Gleichheit, wie du zeigen sollst). Sie wird aber nicht verkleinert, und das ist hier der springende Punkt.
> was die Inklusion ja erlaubt. Von zweiter
> Menge auf die dritte Menge, wird die Menge durch das
> konkatenierte L2* und L1* auch nur größer. Danach wird
> nur noch die Vereinigung auf die jeweils beiden
> konkatenierten Mengen angewendet und die Vereinigung mache
> die Menge auch nur größer. Danach ist man aber dann bei
> der Form wie bei Aussage 2 auf der rechten Seite gefordert
> wird!
>
> Er meinte dann: Die Rückrichtung, also das
> bekäme ich sicher selber hin. Und jetzt bin ich wieder
> genau da, wo ich vor ein paar Tagen hier eigentlich gefragt
> hatte; nämlich bei:
>
> 2.) [mm]"\supseteq"[/mm]:
>
> Also muss ich hier jetzt irgendwie sowas zeigen wie
> [mm](L_1^{\star} \cdot L_2^{\star})^{\star} \subseteq (L_1 \cup L_2}^{\star})[/mm]...
Du musst genau das zeigen, und sonst nichts. Und fang ja nicht wieder die Inklusionskette mit genau diesen beiden Inklusionen an :)
> > Versuch es doch mal allgemein zu zeigen. Sei [mm]w \in (L_1 \cup L_2)^\ast[/mm].
> Dann gibt es ein [mm]n \in \IN[/mm] ([mm]n = 0[/mm] ist auch >moeglich!)
> > und [mm]w_1, \dots, w_n \in L_1 \cup L_2[/mm] mit [mm]w = w_1 \cdots w_n[/mm].
> > Wenn du jetzt argumentierst, dass [mm]w_i[/mm] auch in [mm]L_1^\ast \cdot L_2^\ast[/mm]
> liegt,
> > bekommst du so [mm](L_1 \cup L_2)^\ast \subseteq (L_1^\ast \cdot L_2^\ast)^\ast[/mm]
> gezeigt.
>
> Kann man das jetzt nicht auch auf die "Rückrichtung"
> anwenden? Denn du hast das ja jetzt für die Richtung
> gemacht, für die ich die Lösung vom Prof. bekommen hab...
Direkt anwenden nicht, aber die Rueckrichtung geht aehnlich. Ist ein wenig komplizierter, aber durchaus machbar.
Zeige doch erstmal [mm] $L_1^\ast \cdot L_2^\ast \subseteq (L_1 \cup L_2)^\ast$, [/mm] das ist nicht ganz so schwer.
LG Felix
|
|
|
| |
|
[mm](L_1 \cup L_2)^{\star} \subseteq (L_1^{\star} \cup L_2^{\star})^{\star} \subseteq((L_1^{\star} \cdot L_2^{\star}) \cup (L_2^{\star} \cdot L_1^{\star}))^{\star} \subseteq (L_1^{\star} \cdot L_2^{\star})^{\star}[/mm]
Ich hab's auf meinem Block hier sogar stehen. War wohl ein Tipfehler!
Du meinst also, ich soll erst das hier zeigen: [mm] $(L_1^\ast \cdot L_2^\ast) \subseteq (L_1 \cup L_2)^\ast$
[/mm]
Ich muss erst ein Element y definieren, dass in der linken Menge der Aussage liegt, die ich zeigen will:
[mm] $\exists [/mm] i,j [mm] \in \mathbb [/mm] N$ sowie [mm] $l_1 \in L_1^i, l_2 \in L_2^j$, [/mm] so dass $x = [mm] l_1 \cdot l_2$
[/mm]
Und dann muss ich noch ein Element definieren, dass in der rechten Menge der Aussage liegt, die ich zeigen will:
[mm] $l_1 \in L_1 \text{ und } l_2 \in L_2 \text{ so dass } [/mm] y = [mm] l_1 \cup l_2$
[/mm]
Nun fehlt noch der äußere Kleene-Stern der rechten Menge: [mm] $\exists i\in \mathbb [/mm] N [mm] y^i$
[/mm]
Aber wie geht's hier nun weiter?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 So 14.07.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:01 Do 11.07.2013 | | Autor: | felixf |
Moin!
> Nehmen wir [mm]L_1 = \{a\}[/mm] und [mm]L_2 = \{b\}[/mm]. Dann ist
> [mm]L_1^\ast = \{e, a, aa, aaa, aaaa, \dots \}[/mm] und [mm]L_2^\ast = \{e, b, bb, bbb, bbbb, \dots \}[/mm].
>
> Nun bilde ich die Vereinigung. Links habe ich:
> [mm](L_1 \cup L_2)^\ast = \{e, a, b, ab, ba, aaa, aab, aba, baa,bab, bba, bbb, aaaa, aaab, \dots \}[/mm]
>
> und rechts:
> [mm](L_1^\ast * L_2^\ast)^\ast = \{e, a, b, ab,aaa, aab, abb, bbb, aaab, aabb, abbb, bbbb, \dots \}[/mm]
>
> Ich habe die Wörter mal der Länge nach sortiert. Ich
> hoffe es wird klar, dass z.B. [mm]aba[/mm] nicht auf der rechten
> Seite vorkommt. Oder habe ich etwas übersehen?
Du hast was uebersehen: $aba = (a [mm] \cdot [/mm] b) [mm] \cdot [/mm] (a [mm] \cdot \epsilon)$ [/mm] liegt ebenfalls in der Menge auf der rechten Seite. :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:10 Do 11.07.2013 | | Autor: | Micha |
Hi Felix,
sowas hatte ich schon vermutet. War aber wohl etwas zu verwirrt. Danke!
Gruß Micha
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:59 Do 11.07.2013 | | Autor: | felixf |
Moin,
> Beweisen Sie folgende Aussage [mm](L_1 \cup L_2)^{\star} = (L_1^{\star} \cdot L_2^{\star})^{\star}[/mm]
es waere schon nett, wenn du auf fast gleiche Fragen hier im Forum verweisen wuerdest, die du schonmal gestellt hast. Zum Beispiel in diesem Thread!
LG Felix
|
|
|
|
