Was bedeutet der Pfeil ?? →
Wenn y=f(x) einen funktionalen Zusammenhang bezeichnet, also eine Abbildung, Transformation, Funktion, Operation, … und x Werte aus einer Menge X durchläuft und dabei nur Werte y aus einer Menge Y entstehen, dann schreibt oder deklariert man diese Funktion durch die Schreibweise f:X→Y, f bildet X in Y ab.
Was bedeutet X*, Y*, C ?
In Deinem Themengebiet sind die Mengen X und Y Zeichenvorräte. Zeichen kann alles Mögliche sein, nicht nur Buchstaben. X* bezeichnet dann die Menge der Worte über X, also alle Zeichenketten, die irgendwie, erstmal ohne Sinn und Verstand, aus den Zeichen von X gebildet werden können. Y* genauso für die Zeichen von Y.
Definition:
Codierung Seien X und Y zwei Alphabete, dann heißt jede
eindeutige Abbildung C mit
C : X* →Y*
Codierung von X* in Y*.
C ist nun so eine Abbildung, die wild Worten aus Zeichen in X Worte in Zeichen von Y zuordnet.
Definition: Homomorphe Codierung
Eine Codierung C : X* → Y* heißt homomorph, falls für alle p,
q aus X* gilt:
C(p ◦ q) = C§ ◦ C(q).
Die Bedingung der Homomorhpie sagt, dass die Zuordnung nicht ganz so wild sein darf. Genauer gesagt lässt sich die Zuordnung der Worte auf die Zuordnung der einzelnen Zeichen zurückführen. Aber Vorsicht, es ist nicht Zeichen auf Zeichen. Sondern jedem Zeichen in X wird ein Wort in Y zugeordnet. Das kann auch aus null oder einem einzelnen Zeichen bestehen. Unter der Abbildung C wird dann jedes Zeichen z in einem Wort w aus X* durch die zugeordnete Zeichenkette C(z) ersetzt.
Probiere jetzt nochmal die Aufgabe. C(aa) ist immer C(a)C(a), C(aba) muss die Form C(a)C(b)C(a) haben. Vorsicht, ist C(a) das Nullwort, dann ist es im Ergebnis nicht sichtbar.
Können die Codierungen C1, C2, C3, : {a, b}* → {0, 1}*
von denen Sie wissen, dass:
(a) C1(aa) = 001100
(b) C2(aa) = 010010
© C3(aba) = 010011
homomorph sein?
Gruß, Lutz
