Alphabet/Wörter/Rekursive Definition/Beispiel

Die Menge der Wörter über einem Alphabet ${}A$ kann man auch folgendermaßen rekursiv definieren.

1. ${}\emptyset$ ist ein Wort über ${}A$.
2. Wenn ${}x$ ein Wort ist und ${}a\in A$ ein Buchstabe, so ist auch ${}xa$ ein Wort.

Hier repräsentiert ${}x$ (eine Variable) ein beliebiges schon konstruiertes Wort. Dabei ist ${}\emptyset a$ als ${}a$ zu lesen, sodass die beiden erlaubten Konstruktionsschritte (also der Anfangsschritt und der Rekursionsschritt) sichern, dass die einzelnen Symbole aus ${}A$ Wörter sind. Wenn das Alphabet durch ${}A=\{a,b,c\}$ gegeben ist, so würde der rekursive Nachweis, dass ${}abbac$ ein Wort ist, folgendermaßen gehen.

1. Wegen der Anfangsbedingung ist ${}\emptyset$ ein Wort.
2. Deshalb und wegen des Rekursionsschrittes ist ${}\emptyset a=a$ ein Wort.
3. Deshalb und wegen des Rekursionsschrittes ist ${}ab$ ein Wort (hier ist also ${}x=a$ das schon nachgewiesene Wort und der Buchstabe ${}b$ wird angehängt).
4. Deshalb und wegen des Rekursionsschrittes ist ${}abb$ ein Wort (hier ist also ${}x=ab$ das schon nachgewiesene Wort und der Buchstabe ${}b$ wird angehängt).
5. Deshalb und wegen des Rekursionsschrittes ist ${}abba$ ein Wort (hier ist also ${}x=abb$ das schon nachgewiesene Wort und der Buchstabe ${}a$ wird angehängt).
6. Deshalb und wegen des Rekursionsschrittes ist ${}abbac$ ein Wort (hier ist also ${}x=abba$ das schon nachgewiesene Wort und der Buchstabe ${}c$ wird angehängt).