Beweis eines Homomorphismus

vip*r

Hey Leute!

Ich hab mit dem untenstehenden mal versucht einen Homomorphismus zwei Sprachen zu beweisen. Findet ihr, dass das soweit richtig ist?

Aufgabe:

Beweisen oder widerlegen Sie die folgende Aussage:

Seien L1 Teilmenge von Σ^*_Bool und L2 Teilmenge von Σ^*_Bool reguläre Sprachen und h: Σ^*_Bool→Σ^*_Bool ein Homomorphismus. Dann gilt: h(L1.L1) = h(L1) . h(L2) mit h(L) = {h(w) | w in L}

Anmerkung: Der . soll den Konkatenationspunkt darstellen.

Mein Beweis:

Sei w in L1 und u in L2 mit w=a₁.a₂ und u=b₁.b₂ mit a₁,a₂,b₁,b₂ in Σ

Beweis über Wortlänge:

Sei nun |w|>m, |u|>n mit m>2 und n>2, also w=a₁.a₂ ... a_n-1.a_n und w=b₁.b₂ ... b_n-1.b_n, dann gilt:

h(L1.L2) = h(L1) . h(L2)
h(w.u) = h(w) . h(u)
h(w.u) = h(a₁.a₂ ... a_n-1.a_n) . h(b₁.b₂ ... b_n-1.b_n)
h(w.u) = h(a₁.a₂ ... a_n-1)h(a_n) . h(b₁.b₂ ... b_n-1)h(b_n)
.
.
.
h(w.u) = h(a₁)h(a₂) ... h(a_n-1)h(a_n) . h(b₁)h(b₂) ... h(b_n-1)h(b_n)

Anmerkung: Der . soll den Konkatenationspunkt darstellen.

Michael E.

vip@r schrieb:

Sei w in L1 und u in L2 mit w=a₁.a₂ und u=b₁.b₂ mit a₁,a₂,b₁,b₂ in Σ

Also sind w und u Wörter der Länge 2.

Beweis über Wortlänge:

Sei nun |w|>m, |u|>n mit m>2 und n>2, also w=a₁.a₂ ... a_n-1.a_n und w=b₁.b₂ ... b_n-1.b_n

Hat dann nichts mit dem vorherigen Satz zu tun. Versuchst du eine Induktion zu machen? Was ist dann mit dem Fall |w| = 2, |u| > 2?

h(L1.L2) = h(L1) . h(L2)
h(w.u) = h(w) . h(u)
h(w.u) = h(a₁.a₂ ... a_n-1.a_n) . h(b₁.b₂ ... b_n-1.b_n)
h(w.u) = h(a₁.a₂ ... a_n-1)h(a_n) . h(b₁.b₂ ... b_n-1)h(b_n)
.
.
.
h(w.u) = h(a₁)h(a₂) ... h(a_n-1)h(a_n) . h(b₁)h(b₂) ... h(b_n-1)h(b_n)

Was ist das hier? Wie ist der Zusammenhang der ersten beiden Zeilen? Was tun die anderen Zeilen? Du hast dein Ziel gar nicht vor Augen.

knivil

mal versucht einen Homomorphismus zwei Sprachen zu beweisen

Das ist nicht die Aufgabenstellung. So wie es dasteht, funktioniert es nur fuer Woerter, die sowohl in L1 als auch in L2 enthalten ist.

Gegenbeispiel:

L1 = {0}, L2 = {1}, h(w) = w (Identitaet)

h(0.0) =  h(0).h(0) Homomorphismus
       =    0 .  0
       =  h(0).h(1)
       =    0 .  1  Widerspruch

vip*r

Ok, dann war das wohl falsch. Wie aber beweiße ich denn dann einen Homomorphismus für 2 Sprachen? Ich hab dann nämlich keine Ideen mehr... Das Problem ist doch egientlich, dass in einer Sprache unendliche viel Wörter enthalten sein können, insbesondere hier wo man ja nicht weiß wie die 2 Sprachen beschaffen sind, oder?

So wie es dasteht, funktioniert es nur fuer Woerter, die sowohl in L1 als auch in L2 enthalten ist.

Beziehst du das auf die Aufgabenstellung oder auf meine "Lösung"?

Michael E.

vip@r schrieb:

Ok, dann war das wohl falsch. Wie aber beweiße ich denn dann einen Homomorphismus für 2 Sprachen?

Erster Schritt: Präzise ausdrücken. Einen Homomorphismus kann man nicht beweisen. Ein Homomorphismus ist eine Funktion mit zusätzlicher Eigenschaft. Du kannst höchstens zeigen, dass eine Funktion ein Homomorphismus ist.

Zweiter Schritt: Mit Kommilitonen zusammensetzen.

(Dritter Schritt: Google fragen. Das ist nicht gerade eine seltene Aufgabe.)

Beziehst du das auf die Aufgabenstellung oder auf meine "Lösung"?

In der Aufgabenstellung hast du nen Tippfehler.

vip*r

Erster Schritt: Präzise ausdrücken. Einen Homomorphismus kann man nicht beweisen.

Dann sind anscheinend die Aufgaben meines Professors alle "falsch gestellt".

Ich hab die Aufgabenstellung jetzt nochmals überprüft. Ich hab keinen Tippfehler oder dergleichen drin. Das einzige was anders gegenüber der Aufgabenstellung ist, dass ich anstelle des Teilmengensymbols eben Teilmenge schreiben muss, weil ich kein Teilmengensymbol gefunden habe. Ist das vielleicht der Fehler?

Michael E.

vip@r schrieb:

Erster Schritt: Präzise ausdrücken. Einen Homomorphismus kann man nicht beweisen.

Dann sind anscheinend die Aufgaben meines Professors alle "falsch gestellt".

Das sehe ich bei obiger Aufgabenstellung nicht.

Edit: Na gut, ich lass mich dazu bequatschen, die Formulierung als Abkürzung für "Beweise die Homomorphismuseigenschaft" zu verwenden. Ich bin noch nicht lange genug im Geschäft, um alle Ausdrucksweisen zu kennen. Schön finde ichs trotzdem nicht.

Ich hab die Aufgabenstellung jetzt nochmals überprüft. Ich hab keinen Tippfehler oder dergleichen drin. Das einzige was anders gegenüber der Aufgabenstellung ist, dass ich anstelle des Teilmengensymbols eben Teilmenge schreiben muss, weil ich kein Teilmengensymbol gefunden habe. Ist das vielleicht der Fehler?

Meinst du wirklich h(L1.L1) = h(L1) . h(L2)? Man beachte das zweite L1.

vip*r

Nein, das muss natürlich h(L1.L2) heißen...

knivil

Wo ist denn das Problem? Dort stehen 2 Saetze: Erster Satz ist die Voraussetzung. Zweiter Satz ist die Behauptung oder was zu zeigen ist. Der Begriff Homomorphismus steht im ersten Satz, ist also Teil der Voraussetzung. D.h. du sollst die Eigenschaften des Homomorphismus benutzen. Selbst nach deiner Korrektur ist der Beweis voellig trivial.

Dann sind anscheinend die Aufgaben meines Professors alle "falsch gestellt".

Natuerlich liegt das Problem bei deinem Professor, der das schon Jahrzehnte macht. Dich trifft keine Schuld.

C++ Forumbot

Dieser Thread wurde von Moderator/in Marc++us aus dem Forum Rund um die Programmierung in das Forum Mathematik und Physik verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.