Ich bekam per Mail folgende Frage zur Aufgabe 8.2:

eine Frage zum FGI2-Zettel 8: Sind in Aufgabe 8.2 die Klammerungsvarianten mit nur einem Klammernpaar gemeint? Ansonsten kämen wir für n=3 auf K(3)=6, nicht K(3)=5 [was rechnerisch laut Rekursionsformel richtig ist], Möglichkeiten:

• a·b·(c·d)
• a·(b·c)·d
• (*) (a·b)·(c·d)
• (a·b)·c·d
• (a·b·c)·d
• a·(b·c·d)

Ließe man die mit (*) markierte Klammerungsvariante (mit zwei Klammerpaaren) weg, käme die Anzahl wieder hin. Oder haben wir etwas anderes an dieser Stelle übersehen?

Ja. Die Aufgabe ist unter strenger Syntax für BPA-Terme zu verstehen (siehe Definition 4.1, S. 166f.), so dass jede Verwendung der Operatoren Auswahl (+) oder Sequenz (·) ein Klammerpaar benötigt. Von den vorgeschlagenen Varianten zählt daher keine einzige zu den fünf 'offiziellen' Möglichkeiten.

Die fünf Klammerungsvarianten sind:

• (((a·b)·c)·d)
• ((a·(b·c))·d)
• ((a·b)·(c·d))
• (a·((b·c)·d))
• (a·(b·(c·d)))

Edit: Zweite Klammerungsvariante korrigiert

Die 2. Variante hat 4 öffnende und 2 schließende Klammern:)

wie ist das n=3 in eurer Diskussion zu verstehen ?
Ich hätte gedacht, dass n=3 bedeutet, dass die menge 3 elemente hat. Z.b abc und nicht abcd

ok ich habs… die informatiker fangen bei 0 an zu zählen

Da steht auch ein Term a_0 a_1 … a_n