Bijektive Abbildung: Alphabet

Question

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<?>a⁰=w <=> w <?>epsilon =w <=> w

Induktinosschritt:

zu zeigen ist: w<?>aⁿ⁺¹=w

w<?>aⁿ⁺¹=w    <=>  w<?> (aⁿ * a)=w    <=> (gemäß IV) w<?>a=w

Geht mein Ansatz in die Richtige Richtung? Wie führe ich ihn am besten zu Ende?

Comments

Zum Induktionsbeweis nochmal,

Es sei <?> die binäre Operation: <?>: X^* x X^* => X*

Für jedes n Element der natürlichen Zahlen inkl. 0 gilt:

Für jedes w ∈ Xⁿ gilt:
 w <?> aⁿ = w

Wie ist dann w <?> a^{n+1}=w definiert, bekomme die IV nicht unter!?

---

Hier ist ein Bild der Aufgabe, wobei ich nicht der Fragesteller bin (aber die selbe Frage habe):

---

Ich verstehe einfach nicht, was der Sinn solcher Aufgaben sein soll, wenn die scheinen einfach ueber unsere mathematische Kentnisse zu sein. Seit dem Beginn des Semesters war es immer wieder so. Ich weiss weder worin noch an wen das liegt .. uns oder sie.

Answer 1

Ich zeig mal den ersten Teil der a) Den Rest tu ich mir nicht an, die Aufgabe ist nervige Schreibarbeit.

Hinweis: Da das LaTeX hier offenbar den Befehl \astrosun,  der den Kreis mit dem Punkt innen drin, nicht kennt verwende ich stattdessen \oplus \( \oplus \).

baac und aaaa sind beide nicht das leere Wort (wir sind also im zweiten Fall). Also haben wir b(aac) und a(aaa)

γ^-1(b) + γ^-1 (a)=1+0=1

γ(1)=b.

Also ist  \( baac \oplus aaaa = b(aac \oplus aaa) \)

Das Spiel wiederholt sich mit dem Term in der Klammer:

γ^-1(a) + γ^-1 (a)=0+0=0

γ(0)=a.

Also ist  \( baac \oplus aaaa = b(aac \oplus aaa) = ba (ac\oplus aa ) \)

Nächste Runde wie oben

\( baac \oplus aaaa = b(aac \oplus aaa) = ba (ac \oplus aa ) =baa (c \oplus a  \)

Weiter im Text:

γ^-1(c) + γ^-1 (a)=2+0=2

γ(2)=c.

Also ist  \( baac \oplus aaaa = b(aac \oplus aaa) = ba (ac \oplus aa ) =baa (c \oplus a )=baac (\epsilon \oplus \epsilon) =baac \epsilon =baac \)

Comments

Von meiner Seite auf jeden Fall dankeschön. :)

Eine Frage bleibt mir dazu leider noch

y^-1(b)+y^-1(c) = 1+2=3

y(3) = {} , also das leere Wort?

Kommt in den anderen beiden Aufgaben von a öfter mal vor, weiß jetzt nicht genau wie ich damit umgehen soll...

---

Nein. 3 =0 mod 3

Ich habe das mod 3 oben nur jeweils weggelassen weiles keinen Unterschied gemacht hat.

---

Wie stellt sich das dann im Ergebnis dar?

Bei der zweiten hat man beispielsweise cbb bis dann y(3) kommt. Also cbb0mod3 oder wie?

Und wie stell ich es dar wenn am Ende zwei Buchstaben übrig bleiben?

---

Auf die Zahlen modulo 3 wird doch nochmal γ angewandt.

Wenn eines der beiden Wörter das leere Wort ist, tritt der erste Teil der Fallunterscheidung in der Defintion ein.

---

Ach Gott ja jetzt check ich es. Danke!