ich sitzte an folgender Aufgabe:
Aufgabenstellung:
Sei \( A=\{a, b\} \) ein Alphabet. Gegeben eine Abbildung \( s: \mathbb{N}_{0} \rightarrow\{0,1\} \), definieren wir eine Abbildung \( f_{s}: A^{*} \times \mathbb{N}_{0} \rightarrow A^{*} \) wie folgt:
\( \begin{array}{c} \forall i \in \mathbb{N}_{0}: f_{s}(\varepsilon, i)=\varepsilon \\ \forall i \in \mathbb{N}_{0} \forall w \in A^{*} \forall x \in A: f_{s}(x w, i)=\left\{\begin{array}{ll} x f_{s}(w, i+1), & \text { wenn } s(i)=1 \\ f_{s}(w, i+1), & \text { wenn } s(i)=0 \end{array}\right. \end{array} \)
Für jedes \( i \in \mathbb{N}_{0} \) sei \( s(i) \) wie folgt:
\( s(i)=\left\{\begin{array}{ll} 1, & \text { falls } i \text { ungerade } \\ 0, & \text { falls } i \text { gerade } \end{array}\right. \)
Berechnen Sie \( f_{s}(w, 0) \) Schritt für Schritt für jedes \( w \in\{\mathrm{a}, \mathrm{bb}, \mathrm{ababb}\} \). Hinweis. Wenden Sie bei jedem Schritt die Definition von \( f_{s} \) höchstens einmal an.
Lösung:
\( f_{s}(\mathrm{a}, 0)=f_{s}(\varepsilon, 1)=\varepsilon \)
\( f_{s}(\mathrm{bb}, 0)=f_{s}(\mathrm{~b}, 1)=\mathrm{b}_{s}(\varepsilon, 2)=\mathrm{b} \)
\( f_{s}(\mathrm{ababb}, 0)=f_{s}(\mathrm{babb}, 1)=\mathrm{b} f_{s}(\mathrm{abb}, 2)=\mathrm{b} f_{s}(\mathrm{bb}, 3)=\mathrm{bb} f_{s}(\mathrm{~b}, 4)=b \mathrm{bb} f_{s}(\varepsilon, 5)=\mathrm{bb} \)
Mein Verständnisproblem:
Wie finde ich heraus, was in \(f_{s}(x w, i) \) mein \(x\), und was mein \(w\) ist? Ich wäre eigentlich davon ausgegangen, dass für die erste Teilaufgabe, also \(w = a\), \(f_{s}(x a, i) \) gelten würde. Aber was ist dann mein \(x\)?
Für die erste Teilaufgabe hätte ich dementsprechend eine andere Lösung erwartet:
\(f_{s}(x a, 0) \) = \(f_{s}(a, 1) \) = \(x f_{s}(a, 2) \) usw., was ja aber offensichtlich nicht zu stimmen scheint.
