Text erkannt:
Aufgabe 3
(5 Punkte)
Wir fixieren zwei Wörter \( u=a a a \) und \( v=b b b b b b \) über dem Alphabet \( \Sigma=\{a, b\} \).
Sei \( L(n) \) die Menge der Wörter der Länge \( n \) über \( \Sigma \), die man durch beliebig häufige Konkatenation von u und \( v \) konstruieren kann.
Beispiel :
\( L(9)=\{\text { aaaaaaaa }, \text { bbbbbbaaa, } a a a p b b b b b\} \text { mit }|L(9)|=3 \)
Definieren Sie eine Funktion \( A: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0} \) rekursiv, so dass \( |L(n)|=A(n) \) für alle \( n \in \mathbb{N}_{0} \) gilt. Tragen Sie hierfür Ihre Definition in folgende Vorlage ein, wobei Sie außer im letzten Fall die konkreten numerischen Werte angeben können:
\( A(n) = \left. {\begin{array}{l} \frac{0}{\square} \\ \frac{1}{\hline 2} \\ \frac{2}{L(n-3)+L(n-6)} \end{array}\right. \)
falls \( n<3 \)
falls \( n=3 \)
falls \( 3<n<6 \)
falls \( n=6 \)
falls \( n>6 \)
Beweisen Sie nun die Korrektheit Ihrer Definition mittels einer geeigneten Induktion nach \( n \), wobei Sie alle Fälle \( n \leq 6 \) in der Induktionsbasis prüfen können. Verwenden Sie folgende Textbox für Ihren Induktionsbeweis:
Antwort:
Wie soll ich dann meine Definition durch Induktion zeigen?
Außerdem, sollte L(n = 0) nicht 1 ergeben, damit auch der Induktionbasis stimmen kann?
