Alphabet/Wörter/Rekursive Definition/Beispiel

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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

  1. ist ein Wort über .
  2. Wenn ein Wort ist und ein Buchstabe, so ist auch ein Wort.

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

  1. Wegen der Anfangsbedingung ist ein Wort.
  2. Deshalb und wegen des Rekursionsschrittes ist ein Wort.
  3. Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).
  4. Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).
  5. Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).
  6. Deshalb und wegen des Rekursionsschrittes ist ein Wort (hier ist also das schon nachgewiesene Wort und der Buchstabe wird angehängt).