100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 5: Kellerautomaten

Der vorliegende Vorlesungszuschnitt beschäftigt sich mit dem Berechnungsmodell der Kellerautomaten, die eine Erweiterung der endlichen Automaten bilden, indem diesen ein unendliches Speicherband (?Keller?) hinzugefügt wird. Der Keller wird ausschließlich nach einem Last-In-First-Out-Prinzip (LIFO-Prinzip) genutzt. Die Aufzeichnung geht darauf ein, welche Sprachklassen durch Kellerautomaten akzeptiert werden und wie sich Kellerautomaten in die Chomsky-Hierarchie einordnen lassen. In diesem Zusammenhang wird auch der Unterschied zwischen deterministischen und nichtdeterministischen Kellerautomaten untersucht.