Weitere Sprachklassen und Turingmaschinen
Worum geht es hier?

Auch Kellerautomaten können nicht jede formale Sprache erkennen. In diesem Kapitel lernst du mit der Turingmaschine ein weiteres Automatenmodell kennen und beschäftigst dich mit kontextsensitiven und rekursiv aufzählbaren Sprachen. Dabei erweiterst du den Blick auf die bisher betrachteten Sprachklassen.
Hier lernst du ...
- ... wie eine Turingmaschine mit Zuständen, einem Schreib-Lese-Kopf und einem Speicherband arbeitet.
- ... wie du die Verarbeitung eines Wortes durch eine Turingmaschine nachvollziehst.
- ... welche Automatenmodelle zu kontextsensitiven und rekursiv aufzählbaren Sprachen gehören.
- ... warum eine Turingmaschine beim Erkennen einer Sprache nicht für jedes Eingabewort anhalten muss.