Formale Sprachen klassifizieren
Worum geht es hier?

Welche formalen Sprachen kann ein endlicher Automat erkennen, und wann braucht man ein leistungsfähigeres Modell? In diesem Kapitel untersuchst du verschiedene Sprachklassen und lernst die zugehörigen Grammatiken und Automaten kennen. Am Ende fasst du diese Zusammenhänge in einer Übersicht zusammen.
Hier lernst du ...
- ... warum endliche Automaten nicht jede formale Sprache erkennen können.
- ... wie formale Sprachen anhand ihrer Grammatiken und der zugehörigen Automaten in Sprachklassen eingeteilt werden.
- ... welche Möglichkeiten und Grenzen endliche Automaten, Kellerautomaten und Turingmaschinen haben.