Motivation

Zu jedem regulärem Ausdruck existiert ein endlicher Automat, welcher die zugehörige Sprache akzeptiert. Aufgrund der 'Trivialität' der regulären Sprachen sind die Möglichkeiten dieser stark eingeschränkt. So ist z.B. die Sprache , erzeugt durch die Grammatik nicht regulär¹. Diese Sprache ist kontextfrei und einen sie akzeptierenden Automat kann durch Erweiterung des endlichen Automaten um einen zusätzlichen Speicher gebastelt werden: Dem Automaten wird ein zusätzliches Band spendiert, allerdings mit der Einschränkung das dieses nur als Stack benutzt wird. Desweiteren funktioniert das Eingabeband als ROM, d.h. es kann nur gelesen werden. Im Gegensatz zu Regelsystemen, die formale Sprachen als Wortmengen erzeugen können, ist der Kellerautomat ein echter Ja/Nein-Sager: Zu einem gegebenen Wort, welches auf das Eingabeband geschrieben wird, entscheidet der Automat mittels einer Überführungsfunktion, ob dieses Wort zu der definierten Sprache gehört. Solche Systeme bezeichnet man als Akzeptoren. Als Anwendungsgebiet dieser Sprachen ist vor allem die BACKUS-NOUR-FORM (BNF) zu nennen, da diese vor allem bei der Syntaxdefinition von Programmiersprachen verwendet wird.