Kleenesche Hülle < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:25 Mi 10.04.2013 | | Autor: | bandchef |
| Aufgabe | Zeigen oder widerlegen sie die folgenden Aussagen:
1.) [mm] $\left( L_1 \cup L_2 \right)^{\star} [/mm] = [mm] L_1^{\star} \cup L_2^{\star}$
[/mm]
2.) [mm] $\left( L_1 \cup L_2 \right)^{\star} [/mm] = [mm] \left( L_1^{\star} \cdot L_2^{\star} \right)^{\star}$ [/mm] |
Hi Leute!
Ich hab mir natürlich zu obiger Aufgabe schon Gedanken gemacht:
[mm] $\left( L_1 \cup L_2 \right)^{\star} [/mm] = [mm] \bigcup_{i \in \mathbb N} \left( L_1 \cup L_2 \right)^i [/mm] = [mm] \bigcup_{i \in \mathbb N} \left( L_1^i \cup L_2^i \right) [/mm] = [mm] \bigcup_{i \in \mathbb N} \left( L_1^i \right) \cup \bigcup_{j \in \mathbb N} \left( L_2^j \right) [/mm] = [mm] L_1^{\star} \cup L_2^{\star}$
[/mm]
Hab ich die erste Aussage SO richtig gezeigt? Kann mir das jemand beantworten?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:18 Mi 10.04.2013 | | Autor: | bandchef |
Habe ein kleines Edit an der Rechnung durchgeführt. Ich denke so kann ich meine Überlegung noch ausführlicher darstellen 
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:42 Mi 10.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Zeigen oder widerlegen sie die folgenden Aussagen:
>
> 1.) [mm]\left( L_1 \cup L_2 \right)^{\star} = L_1^{\star} \cup L_2^{\star}[/mm]
>
> 2.) [mm]\left( L_1 \cup L_2 \right)^{\star} = \left( L_1^{\star} \cdot L_2^{\star} \right)^{\star}[/mm]
Sollen [mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] Sprachen sein? Davon gehe ich mal im Folgenden aus.
> [mm]\left( L_1 \cup L_2 \right)^{\star} = \bigcup_{i \in \mathbb N} \left( L_1 \cup L_2 \right)^i[/mm]
Ja.
> $= [mm] \bigcup_{i \in \mathbb N} \left( L_1^i \cup L_2^i \right)$
[/mm]
Im Allgemeinen nein.
> [mm]= \bigcup_{i \in \mathbb N} \left( L_1^i \right) \cup \bigcup_{j \in \mathbb N} \left( L_2^j \right) = L_1^{\star} \cup L_2^{\star}[/mm]
Ja.
> Hab ich die erste Aussage SO richtig gezeigt?
Nein.
Sie ist auch im Allgemeinen falsch. Betrachte mal über dem Alphabet [mm] $\Sigma=\{1,2\}$ [/mm] die Sprachen [mm] $L_1:=\{1\}$ [/mm] und [mm] $L_2:=\{2\}$, [/mm] die jeweils nur ein Wort der Länge 1 enthalten. Wie sehen dann [mm] $L_1^\star$, $L_2^\star$ [/mm] und [mm] $(L_1\cup L_2)^\star$ [/mm] aus?
Für den zweiten Aufgabenteil würde ich nacheinander zeigen, dass die linke Seite der behaupteten Gleichheit eine Teilmenge der rechten Seite ist, und umgekehrt.
Viele Grüße
Tobias
|
|
|
| |
|
Ich hab diese Aufgabe wohl ganz vergessen und bin heute nochmal drüber gestolpert. Ich hab nun den ersten Teil der Aufgabe so gelöst:
Für diese Aufgabe definiere ich mir die zwei Sprachen [mm] $L_1 [/mm] = [mm] \{1\}$ [/mm] und [mm] $L_2=\{2\}$.
[/mm]
Die linke Seite ist ja bei beiden Teilaufgaben gleich:
[mm] $\text{LS }_{1,2} [/mm] = [mm] \left(L_1 \cup L_2\right)^{\star} [/mm] = [mm] \left(\{1\} \cup \{2\}\right)^{\star} [/mm] = [mm] \{1,11,111,...\} \cup \{2,22,222,...\} =\{1,2,12,21,22,...\}$
[/mm]
Die rechte Seite der ersten Teilaufabe:
[mm] $\text{RS }_1 [/mm] = [mm] L_1^{\star} \cup L_2^{\star} [/mm] = [mm] \{1\}^{\star} \cup \{2\}^{\star} [/mm] = [mm] \{1,11,111,...\} \cup \{2,22,222,...\} =\{1,2,11,22,...\}$
[/mm]
Somit gilt bei der ersten Teilaufgabe [mm] $\text{LS}_{1,2} \not= \text{RS}_{1}$
[/mm]
Die rechte Seite der zweiten Teilaufgabe:
[mm] $\text{RS }_2 [/mm] = [mm] \left(L_1^{\star} \cdot L_2^{\star}\right)^{\star} [/mm] = [mm] \left(\{1\}^{\star} \cdot \{2\}^{\star}\right)^{\star} [/mm] = [mm] \left(\{1,11,111,...\} \cdot \{2,22,222,...\}\right)^{\star} [/mm] = [mm] \{1,11,111,... ,2,22,222, ...\}^{\star} [/mm] = [mm] \{1,2,12,21,22,...\}$
[/mm]
Somit gilt bei der zweiten Teilaufgabe [mm] $\text{LS}_{1,2} [/mm] = [mm] \text{RS}_{2}$
[/mm]
Stimmt das so?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Fr 05.07.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
