0 Daumen
33 Aufrufe

Brauche Hilfe bei folgender Aufgabe:


Aufgabe:

Sei \( A \) ein Alphabet. Wir betrachten die Funktion \( \bullet^{R}: A^{*} \rightarrow A^{*} \), die jedem Wort \( w \in A^{*} \) seine Spiegelung \( w^{R} \in A^{*} \) zuordnet. Dieser Operator ist festgelegt für jedes \( w \in A^{*} \) durch
\( \begin{aligned} \left|w^{R}\right| &=|w| \\ w^{R}(i) &=w(|w|-i-1) \quad \text { für alle } 0 \leq i<|w| . \end{aligned} \)
Ein Wort \( w \in A^{*} \) heißt Palindrom, wenn gilt \( w^{R}=w \). Im lateinischen Alphabet sind z. B. \( { }_{, " \text { REGALLAGER" }} \) oder \( { }_{\text {,RACECAR" }} \) "Palindrome. \( P_{A}=\left\{w \in A^{*} \mid w=w^{R}\right\} \) bezeichne die Sprache aller Palindrome über \( A \).


c) Betrachten Sie nun die Sprache \( Q_{A}=\left\{w w^{R} \mid w \in A^{*}\right\} \).
i) Zeigen oder widerlegen Sie: \( Q_{A} \subseteq P_{A} \)
ii) Zeigen oder widerlegen Sie: \( P_{A} \subseteq Q_{A} \)
d) Definieren Sie induktiv eine Folge von Sprachen \( L_{i} \subseteq A^{*} \) mit \( A=\{a, b\} \) und \( i \in \mathbb{N}_{0} \), sodass \( P_{A}=\bigcup_{i=0}^{\infty} L_{i} \).

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community