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.