Kleenesche Hülle? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:42 Sa 10.12.2011 | | Autor: | bandchef |
| Aufgabe | Beweisen sie, dass gilt:
$( [mm] \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} [/mm] = [mm] (\{ a,b \}^2)^{\star} [/mm] $ |
Ich schreib jetzt erstmal die rechte Seite hin:
$( [mm] \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} [/mm] = ( [mm] \{ \epsilon, a, aa, aaa,... \} \cdot \{\epsilon, b, bb, bbb,... \})^{\star} [/mm] = [mm] \{ \epsilon, a, b, ab, abb, abbb, aab, aabb, aabbb, aaab, aaabb, aaabbb \}^{\star} [/mm] = ab, aab, aabb, aabbb, aaab, aaabb, aaabbb, aaaab, aaaabb, aaaabbb, ...$
So, an dieser Stelle hab ich jetzt noch mal einen Kleenestern. Was passiert hier dann mit dem leeren Wert? Das fliegt doch raus, oder? Könnt ihr mir aber sagen warum der raus fliegt? Laut einem Wikipedia-Eintrag ist der Kleene-Stern angewandt auf das leere Wort wieder das leere Wort! Irgendwie verstehe ich das nicht...
Der Kleene-Stern ist ja so definiert:
[mm] $L^{\star} [/mm] := [mm] \bigcup_{i\in\mathbb N_0}L^i$
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:39 So 11.12.2011 | | Autor: | felixf |
Moin!
> Beweisen sie, dass gilt:
>
> [mm]( \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} = (\{ a,b \}^2)^{\star}[/mm]
>
> Ich schreib jetzt erstmal die rechte Seite hin:
Du meinst die linke Seite 
> [mm]( \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} = ( \{ \epsilon, a, aa, aaa,... \} \cdot \{\epsilon, b, bb, bbb,... \})^{\star} = \{ \epsilon, a, b, ab, abb, abbb, aab, aabb, aabbb, aaab, aaabb, aaabbb \}^{\star}[/mm]
Soweit ok.
> [mm]= ab, aab, aabb, aabbb, aaab, aaabb, aaabbb, aaaab, aaaabb, aaaabbb, ...[/mm]
1. Das ist wieder eine Menge, also du musst Mengenklammern verwenden!
2. Wie du schon bemerkt hast, [mm] $\varepsilon$ [/mm] fehlt. Ebenso fehlt etwa das Wort $a = a [mm] \cdot \varepsilon$ [/mm] oder das Wort $b = [mm] \varepsilon \cdot [/mm] b$.
> So, an dieser Stelle hab ich jetzt noch mal einen
> Kleenestern. Was passiert hier dann mit dem leeren Wert?
> Das fliegt doch raus, oder?
Nein, wieso sollte es?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:03 Do 05.01.2012 | | Autor: | bandchef |
Ich hab mir jetzt die Aufgabe nochmals angesehen und hab mir nun gedacht, dass es vielleicht so noch genauer notiert wäre. Stimmt das so?
$ ( [mm] \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} [/mm] = ( [mm] \{ \epsilon, a, aa, aaa,... \} \cdot \{\epsilon, b, bb, bbb,... \})^{\star} [/mm] = [mm] \{ \epsilon, a, b, ab, abb, abbb, ..., aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ... \}^{\star} [/mm] = ... $
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:09 Do 05.01.2012 | | Autor: | felixf |
Moin!
> Ich hab mir jetzt die Aufgabe nochmals angesehen und hab
> mir nun gedacht, dass es vielleicht so noch genauer notiert
> wäre. Stimmt das so?
>
> [mm]( \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} = ( \{ \epsilon, a, aa, aaa,... \} \cdot \{\epsilon, b, bb, bbb,... \})^{\star} = \{ \epsilon, a, b, ab, abb, abbb, ..., aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ... \}^{\star} = ...[/mm]
Ja.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:29 Do 05.01.2012 | | Autor: | bandchef |
So, auch wenn ich den letzten, äußersten Kleene-Stern eigentlich schon mal gemacht habe, möchte ich ihn nochmal durchgehen; so ganz klar ist es mir nämlich noch nicht.
$ ( [mm] \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} [/mm] = ( [mm] \{ \epsilon, a, aa, aaa,... \} \cdot \{\epsilon, b, bb, bbb,... \})^{\star} [/mm] = [mm] \{ \epsilon, a, b, ab, abb, abbb, ..., aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ... \}^{\star} [/mm] = [mm] \{ \epsilon, a, b, ab, abb, abbb, ..., aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ... a, b, aa, bb, aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ..., aaaab, aaaabb, aaaabbb, ...\}$
[/mm]
Stimmt der Kleene-Stern jetzt so? Ich mein, dass das [mm] $\epsilon$ [/mm] ja eigentlich erst mal nochmal alles das "erzeugen" sollte, das was in der Mengenklammer vorher schon drin war, oder? und erst wenn das alles drin ist, kann man mit dem nächsten Buchstaben anfangen. Simmt das so?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:58 Sa 07.01.2012 | | Autor: | felixf |
Moin!
> So, auch wenn ich den letzten, äußersten Kleene-Stern
> eigentlich schon mal gemacht habe, möchte ich ihn nochmal
> durchgehen; so ganz klar ist es mir nämlich noch nicht.
Das so aufzuschreiben ist sehr verwirrend und fuehrt eher dazu, dass man falsche Schluesse zieht.
> [mm]( \{a\}^{\star} \cdot \{b\}^{\star} )^{\star} = ( \{ \epsilon, a, aa, aaa,... \} \cdot \{\epsilon, b, bb, bbb,... \})^{\star} = \{ \epsilon, a, b, ab, abb, abbb, ..., aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ... \}^{\star} = \{ \epsilon, a, b, ab, abb, abbb, ..., aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ... a, b, aa, bb, aab, aabb, aabbb, ..., aaab, aaabb, aaabbb, ..., aaaab, aaaabb, aaaabbb, ...\}[/mm]
Hier hast du z.B. das Wort $abab$ nirgendwo erwaehnt und auch nirgendwo angedeutet.
> Stimmt der Kleene-Stern jetzt so? Ich mein, dass das
> [mm]\epsilon[/mm] ja eigentlich erst mal nochmal alles das
> "erzeugen" sollte, das was in der Mengenklammer vorher
> schon drin war, oder?
Ja.
> und erst wenn das alles drin ist,
> kann man mit dem nächsten Buchstaben anfangen. Simmt das
> so?
Nunja, wie schon gesagt, da fehlt sehr, sehr viel.
Was du aufgelistet hast sieht eher nach [mm] $\{a\}^\ast \cdot \{b\}^\ast$ [/mm] aus. Dass davon nochmal die kleensche Huelle genommen wird hast du offenbar ignoriert, da selbst sowas einfaches wie $abab$ nicht angedeutet wird.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:41 Do 05.01.2012 | | Autor: | bandchef |
Ich hätte hier gleich nochmal eine kleine Aufgabe:
$L = [mm] (\{aa,ab,ba,bb\})^{\star} [/mm] = [mm] \{\epsilon, aa,ab,ba,bb,aaab,aaba,aabb,aaaa,abaa,abab,abba,abbb,baaa,baab,baba,babb,bbaa,bbab,bbba,bbbb\}$
[/mm]
Laut meiner Lösung muss hier kein [mm] $\epsilon$ [/mm] mit rein. Ich denke aber, dass eben schon eins mit rein muss! Ist, nacht der Ausführung des Kleene-Sterns, die Menge nun zu Ende, oder muss man so "Fortführungspünktchen" setzen? Laut Lösung nicht. Das glaub ich der Lösung auch. Wenn die Menge dennoch nicht zu Ende ist weiß ich nicht warum...
Kannst du mir nochmal helfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:00 Sa 07.01.2012 | | Autor: | felixf |
Moin!
> Ich hätte hier gleich nochmal eine kleine Aufgabe:
>
> [mm]L = (\{aa,ab,ba,bb\})^{\star} = \{\epsilon, aa,ab,ba,bb,aaab,aaba,aabb,aaaa,abaa,abab,abba,abbb,baaa,baab,baba,babb,bbaa,bbab,bbba,bbbb\}[/mm]
Das ist falsch. Die linke Menge hat unendlich viele Elemente, die rechte nicht.
> Laut meiner Lösung muss hier kein [mm]\epsilon[/mm] mit rein.
In dem Fall ist die Loesung falsch. Das [mm] $\epsilon$ [/mm] muss bei der kleenschen Huelle immer mit rein.
> Ich denke aber, dass eben schon eins mit rein muss!
Womit du auch Recht hast.
> Ist, nacht
> der Ausführung des Kleene-Sterns, die Menge nun zu Ende,
> oder muss man so "Fortführungspünktchen" setzen?
Da muessen Fortsetzungspuenktchen hin. Die Menge ist schliesslich nicht endlich!
> Laut
> Lösung nicht. Das glaub ich der Lösung auch. Wenn die
> Menge dennoch nicht zu Ende ist weiß ich nicht warum...
Was ist das fuer eine Loesung?
In der kleenschen Huelle sind alle Woerter aus a und b bestehend drinnen, die eine gerade Laenge haben. Das sind unendlich viele.
LG Felix
|
|
|
|
