Beweis eines Homomorphismus < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen oder widerlegen sie die folgende Aussage:
Seien [mm] $L_1 \subset \Sigma^{\star}_\text{Bool}$ [/mm] und [mm] $L_2 \subset \Sigma^{\star}_\text{Bool}$ [/mm] reguläre Sprachen und $h: [mm] \Sigma^{\star}_\text{Bool} \rightarrow \Sigma^{\star}_\text{Bool}$ [/mm] ein Homomorphismus. Dann gilt: [mm] $h(L_1 \cdot L_2) [/mm] = [mm] h(L_1 \cdot L_2)$ [/mm] |
Mein Versuch für den Beweis:
Sei $w [mm] \in L_1$ [/mm] und $u [mm] \in L_2$ [/mm] mit $w = [mm] a_1 \cdot a_2$ [/mm] und $u= [mm] b_1 \cdot b_2$ [/mm] mit [mm] $a_1, a_2, B_1, [/mm] und [mm] b_2 \in \Sigma$.
[/mm]
Beweis über Wortlänge:
Sei nun $|w|>m$ und $|u|>n$ mit m>2 und n>2, also [mm] $w=a_1 \cdot a_2 \cdot [/mm] ... [mm] \cdot a_{n-1} \cdot a_n$ [/mm] und [mm] $u=b_1 \cdot b_2 \cdot [/mm] ... [mm] \cdot b_{n-1} \cdot b_n$, [/mm] dann gilt:
[mm] $h(L_1 \cdot L_2) [/mm] = [mm] h(L_1) \cdot h(L_2)$
[/mm]
$h(w [mm] \cdot [/mm] u) = h(w) [mm] \cdot [/mm] h(u)$
$h(w [mm] \cdot [/mm] u) = [mm] h(a_1 \cdot a_2 \cdot [/mm] ... [mm] \cdot a_{n-1} \cdot a_n) \cdot h(b_1 \cdot b_2 \cdot [/mm] ... [mm] \cdot b_{n-1} \cdot b_n)$
[/mm]
$h(w [mm] \cdot [/mm] u) = [mm] h(a_1 \cdot a_2 \cdot [/mm] ... [mm] \cdot a_{n-1}) h(a_n) \cdot h(b_1 \cdot b_2 \cdot [/mm] ... [mm] \cdot b_{n-1}) h(b_n)$
[/mm]
.
.
.
$h(w [mm] \cdot [/mm] u) = [mm] h(a_1) h(a_2) \cdot [/mm] ... [mm] \cdot h(a_{n-1}) h(a_n) \cdot h(b_1)h(b_2) \cdot [/mm] ... [mm] \cdot h(b_{n-1}) h(b_n)$
[/mm]
Ist das richtig?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Mi 22.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
