regulärer Ausdruck < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:54 Do 14.06.2012 | | Autor: | bandchef |
| Aufgabe | | Beweisen oder widerlegen Sie: [mm] $\left(\{a\}^\star \{b\}^\star\right)^\star=\left( \{a,b \}^2 \right)^\star$ [/mm] |
Hi Leute!
Ich hab diesen regulären Ausdruck gegeben und soll nun die Gleichheit beweisen. Ich weiß aber nicht wie das gehen soll. Links hab ich einen regulären Ausdruck; aber rechts doch nicht, oder? Rechts steht doch einfach die Potenz der Menge {a,b}...
Irgendwie versteh ich das nicht so ganz!
|
|
| |
|
Hiho,
> Ich hab diesen regulären Ausdruck gegeben und soll nun die
> Gleichheit beweisen. Ich weiß aber nicht wie das gehen
> soll. Links hab ich einen regulären Ausdruck;
Aha, drück den mal bitte in Worten aus, was dieser reguläre Ausdruck genau bedeutet.
> aber rechts doch nicht, oder?
Doch.
> Rechts steht doch einfach die Potenz der Menge {a,b}...
Nein, dazu die Rückfrage an dich: Was bedeutet denn [mm] $\{a\}^\*$? [/mm] Analog bedeutet [mm] $\{a\}^2 [/mm] dann eben einfach..... es ist wirklich so einfach :-P
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:59 Fr 15.06.2012 | | Autor: | bandchef |
Also das [mm] $\{a\}^\star [/mm] = [mm] \{\epsilon, a, aa, aaa, aaaa, ...\}. [/mm] Soweit ist mir das schon noch klar.
Das [mm] $\{b\}^\star [/mm] = [mm] \{\epsilon, b, bb, bbb, bbbb, ...\}.
[/mm]
Diese zwei neuen Mengen werden aneinander Konkateniert und wiederum über diese Menge wird wieder diese Kleene'sche Hülle ausgeführt.
[mm] $\{a,b\}^\star [/mm] = [mm] \{aa, ab, ba, bb\}$ [/mm] und dann wieder die Kleene'sche Hülle drum rum.
Soweit kapier ich das schon, aber wie soll ich denn nun zeigen, dass es eben nicht gleich ist? Das sind ja alles unendliche Mengen? Ich kann dann ja nicht einfach drei so Fortsetzungspunkte hinschreiben und sagen, nein, das ist nicht gleich! Mir gehts quasi um den richtigen Formalismus!
|
|
|
| |
|
Hiho,
> Also das [mm]$\{a\}^\star[/mm] = [mm]\{\epsilon, a, aa, aaa, aaaa, ...\}.[/mm]
> Soweit ist mir das schon noch klar.
ok
> Diese zwei neuen Mengen werden aneinander Konkateniert und
> wiederum über diese Menge wird wieder diese Kleene'sche
> Hülle ausgeführt.
>
> [mm]\{a,b\}^\star = \{aa, ab, ba, bb\}[/mm] und dann wieder die
> Kleene'sche Hülle drum rum.
Hm, nein.
Du hast da ne falsche Vorstellung von.
Die Menge [mm] $\{a,b\}$ [/mm] sind eben alle Wörter, die aus a oder b bestehen!
Es gilt zwar, soweit hast du recht:
[mm] $\{a,b\}^\* [/mm] = [mm] \{aa, ab, ba, bb\}^\*$ [/mm]
aber die Grundmengen sind eben doch verschieden, sondern gleich werden sie erst durch den *
Beispielsweise wären die Mengen
[mm] $\{a,b\}^2 [/mm] = [mm] \{aa, ab, ba, bb\}^2$
[/mm]
nicht gleich!
In Worten ist die linke Menge nämlich eben:
"Wähle zwei Elemente aus der Menge [mm] $\{a,b\}$" [/mm] und die rechte wäre:
"Wähle zwei Elemente aus der Menge [mm] $\{aa, ab, ba, bb\}$
[/mm]
Was aber richtig wäre, wäre:
[mm] $\{a,b\}^2 [/mm] = [mm] \{aa, ab, ba, bb\}$
[/mm]
> Soweit kapier ich das schon, aber wie soll ich denn nun zeigen, dass es eben nicht gleich ist? Das sind ja alles unendliche Mengen?
Dass zwei Mengen nicht gleich sind, wäre der einfache Teil an der Geschichte. Dann musst du ja nur ein Element angeben, was in der einen Menge, aber nicht in der anderen ist.
Und so nebenbei: Die Mengen sind gleich.
> Ich kann dann ja nicht einfach drei so Fortsetzungspunkte hinschreiben und sagen, nein, das ist nicht gleich! Mir gehts quasi um den richtigen Formalismus!
Wie schon gesagt: Ungleichheit formal zu zeigen geht am einfachsten über ein Gegenbeispiel.
Gleichheit ist ein bisschen aufwändiger, das geht meist, in dem man erst [mm] $\subseteq$ [/mm] zeigt und dann [mm] $\supseteq$
[/mm]
Da die Kleensche Hülle ein Hüllenoperator ist, reicht es hier zu zeigen, dass der Erzeuger jeder Menge in der anderen drin liegt, also:
1.) Zeige erst: [mm] $\{a,b\}^2 \subseteq \left\{\{a\}^\*\{b\}^\*\right\}^\*$ [/mm] daraus folgt [mm] $\subseteq$ [/mm] (warum?)
2.) Zeige dann: [mm] $\{a\}^\*\{b\}^\* \subseteq \left\{\{a,b\}^2\right\}^\*$ [/mm] daraus folgt [mm] $\supseteq$
[/mm]
MFG,
Gono.
|
|
|
| |
|
Zitat: "Die Menge $ [mm] \{a,b\} [/mm] $ sind eben alle Wörter, die aus a oder b bestehen!"
Das verstehe ich nicht. Ich hätte immer gedacht, die Menge aller Wörter/Zeichenreihen über einem gewissen Alphabet [mm] $\Sigma$ [/mm] werden doch so ausgedrückt: [mm] $\Sigma^\star$, [/mm] in meinem Fall wäre dann das Alphabet [mm] $\Sigma [/mm] = [mm] \{a,b\}$. [/mm] So steht's zumindestens im Hopcroft...
Zusammenfassung:
1.) [mm] $\Sigma [/mm] = [mm] \{a,b\}$: [/mm] Alphabet mit den Symbolen a und b.
2.) [mm] $\Sigma^1 [/mm] = [mm] \{a,b\}^1$: [/mm] Menge von Wörtern/Zeichenreihen die genau [mm] $\{\epsilon,a,b\}$ [/mm] enthält.
3.) [mm] $\Sigma^2 [/mm] = [mm] \{a,b\}^2$: [/mm] Menge von Wörtern/Zeichenreihen die genau [mm] $\{\epsilon,aa,ab,ba,bb\}$ [/mm] enthält.
4.) [mm] $\Sigma^\star [/mm] = [mm] \{a,b\}^\star$: [/mm] Kleene'sche Hülle [mm] $\{\epsilon,aa,ab,ba,bb,...\}$
[/mm]
Edit 1:
Ah! Jetzt glaub ich hab ich's verstanden. Die Menge von Wörtern/Zeichenreihen aus deinem obigen Zitat entspricht meinem 2. Punkt! Es ist ja egal ob ich $ [mm] \{a,b\} [/mm] $ oder [mm] $\{a,b\}^1$ [/mm] schreibe! Das ist aber schon etwas verwirrend, ob nun die Menge des Alphabets gemeint ist, oder ob eine Menge von Wörtern/Zeichenreihen gemeint ist, da dies dann ja eigentlich schlecht bis gar nicht kenntlich gemacht werden kann.
Oder gibt es eine Konvention, die besagt, dass man zur genauen Unterscheidung dieser beiden Fälle das [mm] $\Sigma$, [/mm] im Falle des Alphabets, ohne Exponent schreiben MUSS und, im Falle einer Menge von Wörtern/Zeichenreihen, mit einem Exponenten "gleich eins", also [mm] $\Sigma^1$ [/mm] schreiben MUSS?
Edit 2:
1.) Zeige erst: $ [mm] \{a,b\}^2 \subseteq \left\{\{a\}^\star\{b\}^\star\right\}^\star [/mm] $ daraus folgt $ [mm] \subseteq [/mm] $ (warum?)
Ich muss hier also zeigen, dass [mm] $\{a,b\}^2 [/mm] = [mm] \{aa, ab, ba, bb\}$ [/mm] eine echte Teilmenge von [mm] $\left\{\{a\}^\star\{b\}^\star\right\}^\star$ [/mm] ist. Sprich, [mm] $\{a,b\}^2$ [/mm] ist in [mm] $\left\{\{a\}^\star\{b\}^\star\right\}^\star$ [/mm] enthalten. Mit dem Ausmultiplizieren wird's wohl noch nicht so ganz getan sein. Ich muss ja wohl jetzt noch zeigen, dass diese ausmultiplizierte Menge auch wirklich in der anderen Menge enthalten ist. Aber wie geht das? Die rechte Menge kann ich ja wohl schlecht ausmultiplizieren; da kommt ja eine unendliche Menge raus. Sieht man ja an der kleene'schen Hülle.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 So 17.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
