0 Daumen
403 Aufrufe

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.



Avatar von

1 Antwort

0 Daumen
 
Beste Antwort
... \(f_{s}(x a, i) \) gelten würde.

\(f_{s}(x a, i) \) kann nicht gelten, weil \(f_{s}(x a, i) \) keine Aussage ist.

Stattdessen gilt

        \(0\) ist gerade.

Laut Definition von \(s\) gilt deshalb

        \(s(0) = 0\).

Laut Definition von \(f_s\) gilt deshalb

        \(f_s(a,0) = f_s(a\varepsilon,0) \stackrel{\text{Def. } f_s}{=} f_s(\varepsilon, 0+1) = f_s(\varepsilon, 1) \stackrel{\text{Def. } f_s}{=} \varepsilon\).

Aber was ist dann mein \(x\)?

Laut

        \(\forall i \in \mathbb{N}_{0} \forall w \in A^{*} \forall x \in A: f_{s}(x w, i)=\begin{cases}x f_{s}(w, i+1), & \text { wenn } s(i)=1 \\ f_{s}(w, i+1), & \text { wenn } s(i)=0 \end{cases}\)

ist \(x\in A\). Also ist \(x\) der erste Buchstabe des Wortes.

Avatar von 5,6 k

Danke für die Antwort!

Also ist \(x\) der erste Buchstabe des Wortes.

Ich glaube, hierher stammt mein Verständnisproblem. Woher weiß ich, dass \(x\) der erste Buchstabe des Wortes ist?

\(x\) steht am Anfang des Wortes und \(x\) ist ein Buchstabe.

\(x\) steht am Anfang des Wortes und \(x\) ist ein Buchstabe.

Wieso kann \(x\) nicht z.B. der zweite Buchstabe sein? Wo wird definiert, dass \(x\) am Anfang des Wortes steht?

\(x\) kann nicht der zweite Buchstabe des Wortes sein, weil vor dem \(x\) kein Buchstabe steht.

\(x\) kann nicht der zweite Buchstabe des Wortes sein, weil vor dem \(x\) kein Buchstabe steht.

Heißt das, ich kann nur an \(f_{s}(x w, i) \) und \(x\in A\) festmachen, dass mit \(x\) der erste Buchstabe des Wortes gemeint ist?

Ja, so ist es.

Okay, ich versuche das gerade nachzuvollziehen, hier ist die Begründung die ich mir erschließen konnte:

Bei \(x w \) handelt es sich um eine Konkatenation aus \(x\) und \(w\). Da \(x\) laut Definition nur aus A stammen kann (also nur entweder "a" oder "b" sein kann), kann es sich bei \(x\) maximal immer nur um den ersten Buchstaben der jeweiligen Eingabe in die Funktion handeln.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community