Von Grammatik zu Kellerautomat

Kellerautomaten (PDAs) sind das Automatenmodell der kontextfreien Sprachen. Zu jeder kontextfreien Grammatik kann ein Kellerautomat konstruiert werden, der die gleiche Sprache akzeptiert. Der Kellerautomat simuliert dabei einfach die Ableitung des Wortes durch die Produktionen der Grammatik und vergleicht das Ergebnis mit dem Eingabewort.