Aufgabe:
sind \( X \) und \( Y \) zwei Mengen und \( f: X \rightarrow Y \) eine bijektive Abbildung, so ist die Relation
\( R_{f}=\{(f(x), x) \mid 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 \in X \) und jedes \( y \in 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 \( \gamma \) die bijektive Abbildung
\( \begin{array}{l} \gamma: ~\mathbb{Z}_{3} \mapsto A \\ 0 \mapsto a \\ 1 \mapsto b \\ 2 \mapsto c \end{array} \)
und es sei \( \odot \) die binäre Operation
\( \odot: A^{*} \times A^{*} \rightarrow A^{*} \)
\( (u, v) \mapsto\left\{\begin{array}{ll} 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 x), & \text { falls } u=x \cdot \mu \text { und } v=y \cdot \kappa \\ & \text { für } x, y \in A \text { und } \mu, x \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 Worter der Länge 1 in \( A^{1} \) aufzufassen sind.
a) Berechnen Sie die Worter baac \( \odot \) aaaa, baac \( \odot \) bbbbb 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^{*} \) ein \( v \in A^{*} \) so an, dass \( u \odot v=\mathrm{a}^{|u|} \) gilt.
c) Beweisen Sie durch vollständige Induktion, dass für jedes \( n \in \mathbb{N}_{0} \) gilt:
\( \text { Für jedes } w \in A^{n}: w \odot \mathrm{a}^{n}=w \)
Mein Ansatz:
wenn u= leeres Wort, dann v = leeres Wort, sodass a^0=epsilon ? habe a^´|u| als Anzahl der a aufgefasst?!! Richtig?
Wie mache ich weiter?
- - - - - -
Ansatz (aus Duplikat):
IA: n=0 => w<?>a0=w <=> w <?>epsilon =w <=> w
Induktinosschritt:
zu zeigen ist: w<?>an+1=w
w<?>an+1=w <=> w<?> (an * a)=w <=> (gemäß IV) w<?>a=w
Geht mein Ansatz in die Richtige Richtung? Wie führe ich ihn am besten zu Ende?
