Aufgabenblatt: Grundbegriffe der Informatik
Sind X und Y zwei Mengen und f : X → Y eine bijektive Abbildung, so ist die Relation
$$R _ { f } = \{ ( f ( x ) , x ) | x \in X \}$$
eine bijektive Abbildung von Y nach X, die wir mit f^{-1} bezeichnen, Umkehrabbildung von f oder Inverse von f nennen, und für die für jedes x ∈ X und jedes y ∈ Y gilt:
$$f ^ { - 1 } ( f ( x ) ) = x \text { und } f \left( f ^ { - 1 } ( y ) \right) = y$$
Es sei A das Alphabet {a, b, c}, es sei γ die bijektive Abbildung
$$\begin{aligned} \gamma : \mathbb { Z } _ { 3 } \rightarrow A \\ 0 \mapsto a \\ 1 \mapsto b \\ 2 \mapsto c \end{aligned}$$
und es sei \( \odot \) die binäre Operation
$$\odot : A ^ { * } \times A ^ { * } \rightarrow A ^ { * }$$
$$( u , v ) \mapsto \left\{ \begin{array} { l l } { u , } & { \text { falls } u = \epsilon \text { oder } v = \epsilon } \\ { \gamma \left( \left( \gamma ^ { - 1 } ( x ) + \gamma ^ { - 1 } ( y ) \right) \bmod 3 \right) \cdot ( \mu \odot \kappa ) , } & { \text { falls } u = x \cdot \mu \text { und } v = y \cdot \kappa } \\ { } & { \text { für } x , y \in A \text { und } \mu , \kappa \in A ^ { * } } \end{array} \right.$$
wobei für jede nicht-negative ganze Zahl z der Ausdruck z mod 3 den Rest der ganzzahligen Division von z mit 3 bezeichne und bei Bedarf Zeichen in A als Wörter der Länge 1 in A^{1} aufzufassen sind.
a) Berechnen Sie die Wörter baac \( \odot \) aaaa, baac \( \odot \) bbbbbb und baac \( \odot \) cc
b) Es sei
$$\begin{aligned} \delta : A & \rightarrow A \\ \mathrm { a } & \mapsto \mathrm { a } \\ \mathrm { b } & \mapsto \mathrm { c } \\ \mathrm { c } & \mapsto \mathrm { b } \end{aligned}$$
Geben Sie für jedes \( u \in A ^ { * } \text { ein } v \in A ^ { * } \text { so an, dass } u \odot v = \mathrm { a } ^ { | u | } \).
c) Beweisen Sie durch vollständige Induktion, dass für jedes n ∈ N_{0} gilt:
$$w \in A ^ { n } : w \odot \mathrm { a } ^ { n } = w$$
Quelle: http://gbi.ira.uka.de/aufgaben/blatt-02-aufgaben.pdf
Lösungen: http://gbi.ira.uka.de/aufgaben/blatt-02-loesungen.pdf
