Rekursionsvorschrift/Wörter/Linksseitig doppelt/Aufgabe

Es sei ${}S=\{A,B,C\}$. Betrachte die rekursiv definierte Teilmenge ${}T\subseteq S^{*}$, die wie folgt festgelegt wird.

1. Jedes Element aus ${}S$ gehört zu ${}T$.
2. Wenn ${}X,Y\in T$ sind, so gehört auch ${}XXY$ zu ${}T$.

Bestimme, welche der folgenden Wörter zu ${}T$ gehören.

$A,\,ABABC,\,AABBB,\,AABAABA,\,AAAA,\,AABABAAB,\,AAAAAABBB.$

Zeige die folgenden Aussagen.

1. Jedes Element aus ${}T$ besitzt eine ungerade Wortlänge.
2. Jede ungerade Zahl kommt als Wortlänge eines Elements aus ${}T$ vor.
3. Es gibt Elemente in ${}T$, die auf mehrfache Weise generiert werden können.
4. Jedes Wort ${}t\in T\setminus S$ beginnt mit zwei gleichen Buchstaben.

Eine Lösung erstellen