Wir betrachten die Sprache WAS, die sich anhand der 3 unten aufgeführten Regeln erzeugen lässt:
1. WA ist ein gültiges Wort der Sprache.
2. Wenn xA ein gültiges Wort ist, dann auch xAS.
3. Wenn Wx ein gültiges Wort ist, dann auch Wxx.

Beweisen Sie mit vollständiger Induktion, dass das Wort WS nicht Teil der Sprache WAS ist.

Wie mache ich das denn mithilfe von Induktion?? Vielen Dank schonmal..

Induktionsanfang
die Menge der Wörter, die nur WA enthält (also {WA}) enthält nicht WS

Induktionsschritt:

aus einer Menge von Wörtern, die WS nicht enthält,
kann mit Regel 2 oder Regel 3 keine Wortmenge gewonnen werden die WS enthält