0 Daumen
30 Aufrufe

Bitte um Hilfe bei folgender Aufgabe:


Es sei \( A=\{a, b\} \) ein Alphabet und die Abbildung \( f: A^{*} \rightarrow A^{*} \) wie folgt induktiv definiert:
\( \begin{array}{c} f(\varepsilon)=\varepsilon, \quad f(a)=a, \quad f(b)=b \\ \forall w \in A^{+}: f(w \cdot a)=a \cdot f(w) \\ \forall w \in A^{+}: f(w \cdot b)=f(w) \cdot b \end{array} \)
Außerdem bezeichne \( N_{x}(w) \) die Anzahl der Vorkommen eines Zeichens \( x \in A \) in einem Wort \( w \in A^{*} \).

a) Beweisen Sie durch vollständige Induktion: \( \forall w \in A^{*}: N_{a}(w)=N_{a}(f(w)) \)
b) Sei \( L=\left\{a^{i} b^{j} \mid i, j \in \mathbb{N}_{0}\right\} \) und bezeichne \( f(M)=\{f(w) \mid w \in M\} \) für eine Menge \( M \subseteq A^{*} \).
Beweisen Sie durch vollständige Induktion: \( f\left(A^{*}\right) \subseteq L \)

vor von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community