Zeigen Sie, dass für alle w ∈ A+ gilt:

Question

Hallo zusammen!

Sei A ein Alphabet und h : A ^∗ → A ^∗ ein Homomorphismus. Zeigen Sie, dass für alle  w ∈ A⁺ gilt:

h(w) = h(w(0)) · h(w(1)) · ... · h(w(|w| − 1))

Ich brauche keine Hilfe beim Lösen der Aufgabe, sondern beim Inhalt. Leider habe ich einige Vorlesungen verpasst,als ich krank war und weiß nicht mehr, worum es überhaupt geht.

1. Sei A ein Alphabet:

Also z.B A={a,b,c}

Dann A* ={{}, a , b, c, ab, ac, bc , abc, acb, bac, bca, cab, cba } , richtig?

Was ist aber A⁺ ?

2. h : A^∗ → A^∗ ein Homomorphismus

Ich verstehe überhaupt nicht, was für eine Abbildung h ist. Abbildungen wie g: x |----> x^3  sind verständlich aber h kann ich mir nicht vorstellen. Was genau ist eine Abbildung (btw ich habe mir einige Videos über Abbildung angeschaut, verstehes immernoch nicht.

3. h(w) = h(w(0)) · h(w(1)) · ... · h(w(|w| − 1))

h(w(0)) =         , das leere Wort

h(w(1)) = a oder b oder c

Also h(w) = { ???? }

Was rechnet man hier mit Multiplikation? Konkatenation??

z.B sei w = abc

w(1) = a

w(2) = b

richtig?

Was ist denn h(w(|w| - 1) ?

Comments

Zu 1) A* bezeichnet doch bestimmt die Kleensche Hülle von A

https://de.wikipedia.org/wiki/Kleenesche_und_positive_H%C3%BClle

bei dir fehlen also z.B aa, bb, cc, ca, ba, cb ... Es gibt insgesamt 27 dreistellige Wörter, (aaa, bbb, ccc, aab, aac etc fehlen), alle 4+ stelligen Wörter fehlen

A^+ ist die positive Hülle, das sind alle Wörte von A* Außer das leere Wort!

---

h ist ein Homomorphismus und nicht näher beschrieben. Es gilt aber für alle u,v in A*

h(uv) = h(u)h(v)

Wenn du zwei Wörter aneinender klatschst und dann den Homomorphismus drauf wirfst, kommt dasselbe raus, wie wenn du erst den Homomrphismus auf die beiden Wörter wirfst und dann die Ergebnisse aneinander hängst.

---

Das sollst du jetzt verallgemeinern. Ja die Multiplikation heißt hier "Wörter aneinanderhängen"

Apfel*kuchen = Apfelkuchen

Du sollst jetzt zeigen, wenn du einen Homom hast und ein Wort, dann ist es egal, ob du den Homom auf das gesamte Wort anwendest

oder ob du den Homom erst auf alle Buchstaben des Wort anwendest und dann die erhaltenen Ergbenisse aneinanderfügst diese dann aneinanderfügst.

das heißt ein Homom ist durch sein Verhalten auf dem Alphabet schon auf der gesamten kleenschen Hülle eindeutig festgelegt.

Answer 1

Was ist aber A+ ?

\(A^*\) ist die Menge aller Wörter, die man mit Buchstaben aus \(A\) bilden kann. Dazu gehören nicht nur die von dir genannten, sondern zum Beispiel auch acab.

Wörter können beliebig lang sein, aber nicht unendlich lang.

Abbildungen wie g: x |----> x³ sind verständlich

Mit dem Pfeil \(\mapsto\) wird die Abbildungsvorschrift angegeben. In deinem Fall wird jedes \(x\) aus der Definitionsmenge auf \(x^3\) abgebildet. Also wird zum Beispiel die 4 auf die 64 abgebildet.

Mit dem Pfeil \(\to\) werden Definitionsmenge und Wertebereich angegeben. Die Abbildung \(h\) bildet also Wörter über dem Alphabet \(A\) auf Wörter über dem Alphabet \(A\) ab. Wie die Abbildung \(h\) das genau macht (was also die Abbildungsvorschrift ist) wird in der Aufgabe nicht erwähnt.

Es wird lediglich erwähnt, dass \(h\) ein Homomorphisus ist. Das heißt, wenn das Wort \(v_1\) auf das Wort \(w_1\) abgebildet wird und das Wort \(v_2\) auf das Wort \(w_2\), dann wird das Wort \(v_1v_2\) auf das Wort \(w_1w_2\) abgebildet (das gilt für jedes \(v_1\) und jedes \(v_2\) aus \(A^*\)).

3. h(w) = h(w(0)) · h(w(1)) · ... · h(w(|w| − 1))

\(w(i)\) ist wohl der Buchstabe, der im Wort \(w\) an der Position \(i\) steht (Zählung beginnt bei 0, wie das in ordentlichen Programmiersprachen üblich ist).

Was rechnet man hier mit Multiplikation? Konkatenation??

Ja.

z.B sei w = abc

w(1) = a

w(0) = a

w(1) = b

w(2) = c

|w| = 3 (Länge des Wortes)

Deshalb ist w(|w|-1) = w(3-1) = w(2) der letzte Buchstabe des Wortes.