Kellerautomaten verstehen: Funktionsweise & Anwendungen in der Theoretischen Informatik 📚

Kellerautomaten (PDA) sind die abstrakten Automaten, die genau zu den kontextfreien Sprachen passen. Sie arbeiten mit einem Stack (Stapelspeicher) und können Wörter auf zwei verschiedene Arten akzeptieren. Anders als bei endlichen Automaten gibt es signifikante Unterschiede zwischen den deterministischen und den nichtdeterministischen Varianten. * Das GANZ NEUE Buch: http://weitz.de/GDM/ * Das NEUE Buch: http://weitz.de/PP/ * Skript: http://weitz.de/files/ti-skript.pdf * KORREKTUR: http://weitz.de/corr/HEXk1iByOFw * Das Video im Playlist-Kontext: http://weitz.de/y/HEXk1iByOFw?list=PLb0zKSynM2PDUcEEkjv48Y_4N9CBFyzsz * Liste aller Videos: http://weitz.de/haw-videos/ * Das etwas andere Mathe-Lehrbuch: http://weitz.de/KMFI/ * "FAQ": http://weitz.de/youtube.html 00:00 Was endliche Automaten nicht können 02:39 Stacks (Stapelspeicher) 04:49 Definition der Kellerautomaten 08:19 Beispiel: Wie arbeiten Kellerautomaten? 22:16 Noch ein Beispiel für einen Kellerautomaten 26:06 Nichtdeterminismus bei Kellerautomaten 30:16 Akzeptanz durch Endzustände 35:01 Kellerautomaten und kontextfreie Sprachen 40:41 Deterministische Kellerautomaten (DPDA) 46:42 Eine kontextfreie Sprache, die kein DPDA akzeptiert Corrections: 54:25 Bitte beachten Sie die Korrekturhinweise in der Videobeschreibung.