Zusammenhang zwischen Automaten und Sprachen
Haben wir eine formale Sprache mit Hilfe einer Grammatik spezifiziert, so ist es leicht, beliebig viele Wörter der Sprache zu produzieren. Nicht ganz so einfach ist die Entscheidung, ob ein gegebenes Wort zur Sprache gehört oder nicht (Wortproblem). Im Fall der regulären Sprachen lässt sich das Wortproblem effizient lösen ... durch die Verwendung endlicher Automaten.
Im Fall der kontextfreien Sprachen fehlt uns im Moment noch eine analoge Konstruktion. Die Algorithmen zur Syntaxanalyse kontextfreier Sprachen (siehe Kopien) zeigen, dass es sich um Automaten handeln muss, die rekursive Strukturen verarbeiten können. Eine für solche Fälle geeignete Datenstruktur ist - wie aus dem Kurs Q1 bekannt ist - der Keller (Stapelspeicher); der zugehörige Automat muss also ein Kellerautomat sein. Was also den regulären Sprachen die endlichen Automaten sind, sind den kontextfreien Sprachen die Kellerautomaten.
Kontextfreie Sprachen ... Kellerautomaten
