Homomorphismus < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen oder widerlegen sie:
Seien [mm] $L_1 \subseteq \sum^{\star}_{\text{Bool}}$ [/mm] und [mm] $L_2 \subseteq \sum^{\star}_{\text{Bool}}$ [/mm] reguläre Sprachen und $h : [mm] \sum^{\star}_{\text{Bool}} \rightarrow \sum^{\star}_{\text{Bool}}$ [/mm] ein Homomorphismus. Dann gilt:
[mm] $h(L_1 \cdot L_2) [/mm] = [mm] h(L_1) \cdot h(L_2)$ [/mm] mit $h(L) = [mm] \{h(w) | w \in L\}$ [/mm] |
Hi Leute!
Was ich soweit verstanden habe, sind die Definitionen in der ersten Zeile der Aufgabe.
-> Die Sprache L1 ist eine Teilmenge und stammt aus dem Alphabet L1 das alle Kombination von 0,1 enthält. Genauso bei Sprache L2.
-> Der Homomorphismus "h" bildet von [mm] $\sum^{\star}_{\text{Bool}} [/mm] auf [mm] $\sum^{\star}_{\text{Bool}}$ [/mm] ab. Also quasi, dass nach der Anwendung des Homomorphismus das Ergebnis wieder in [mm] $\sum^{\star}_{\text{Bool}}$ [/mm] liegt.
Ich hab mir dazu jetzt auch schon einiges an Fachliteratur reingezogen, aber so wirklich dahinter steigen tu ich nicht was ich da jetzt beweisen soll. Irgendwie glaub ich häng ich schon an der Aufgabenstellung. Da steht ja eigentlich gar nicht so richtig was man machen soll.
Könnt ihr mir an dieser Stelle weiterhelfen?
|
|
| |
|
Hallo bandchef,
> Beweisen oder widerlegen sie:
>
> Seien [mm]L_1 \subseteq \sum^{\star}_{\text{Bool}}[/mm] und [mm]L_2 \subseteq \sum^{\star}_{\text{Bool}}[/mm]
> reguläre Sprachen und [mm]h : \sum^{\star}_{\text{Bool}} \rightarrow \sum^{\star}_{\text{Bool}}[/mm]
> ein Homomorphismus. Dann gilt:
>
> [mm]h(L_1 \cdot L_2) = h(L_1) \cdot h(L_2)[/mm] mit [mm]h(L) = \{h(w) | w \in L\}[/mm]
?? Da fehlt doch was??
Das ist doch einfach die Homomorphieeigenschaft und die Definition des Bildes von [mm]L[/mm] unter [mm]h[/mm] ...
Gemeint ist sicher: "... dann ist auch [mm]h(L)[/mm] eine reguläre Sprache"
>
> Hi Leute!
>
> Was ich soweit verstanden habe, sind die Definitionen in
> der ersten Zeile der Aufgabe.
>
> -> Die Sprache L1 ist eine Teilmenge und stammt aus dem
> Alphabet L1 das alle Kombination von 0,1 enthält. Genauso
> bei Sprache L2.
> -> Der Homomorphismus "h" bildet von
> [mm]$\sum^{\star}_{\text{Bool}}[/mm] auf
> [mm]\sum^{\star}_{\text{Bool}}[/mm][/mm] ab. Also quasi, dass nach der
> Anwendung des Homomorphismus das Ergebnis wieder in
> [mm]\sum^{\star}_{\text{Bool}}[/mm][/mm] liegt.
>
>
>
>
> Ich hab mir dazu jetzt auch schon einiges an Fachliteratur
> reingezogen, aber so wirklich dahinter steigen tu ich nicht
> was ich da jetzt beweisen soll. Irgendwie glaub ich häng
> ich schon an der Aufgabenstellung. Da steht ja eigentlich
> gar nicht so richtig was man machen soll.
>
> Könnt ihr mir an dieser Stelle weiterhelfen?
Ich denke, du musst versuchen, aus der regulären Grammatik [mm]G_1[/mm] für [mm]L[/mm] eine reguläre Grammatik [mm]G_2[/mm] für [mm]h(L)[/mm] basteln.
Einige Hinweise:
1) [mm]h(\varepsilon)=\varepsilon[/mm], das leere Wort wird auf das leere Wort abgebildet
2) Ist [mm]w=a_1a_2...a_n[/mm] mit [mm]a_i\in\sum_{\text{Bool}}[/mm], so ist [mm]h(w)=h(a_1)h(a_2)...h(a_n)[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:24 Sa 07.01.2012 | | Autor: | felixf |
Moin,
> Ich denke, du musst versuchen, aus der regulären Grammatik
> [mm]G_1[/mm] für [mm]L[/mm] eine reguläre Grammatik [mm]G_2[/mm] für [mm]h(L)[/mm] basteln.
moeglicherweise ist es einfacher, einen nichtdeterministischen endlichen Automaten zu basteln aus den entsprechenden fuer [mm] $L_1$ [/mm] und [mm] $L_2$.
[/mm]
Vielleicht steht das eh schon irgendwo in der Vorlesung, und man muss einfach die passenden Aussagen heraussuchen...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Sa 07.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
