Alphabet/Wörter/Rekursive Definition/Beispiel

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

1. $\mathrm{\varnothing }$ 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 $\mathrm{\varnothing }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 $\mathrm{\varnothing }$ ein Wort.
2. Deshalb und wegen des Rekursionsschrittes ist  $\mathrm{\varnothing }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).