DFA vs. NFA

Wenn es ein Resultat in der Theorie der endlichen Automaten gibt, das den Titel "Klassiker" verdient, dann ist es die Potenzmengenkonstruktion. Wir schauen sie uns an, rechnen mehrere Beispiele und beweisen ihre Korrektheit. Und wie einer der Schöpfer dieser Theorie sagte: "It's a trivial proof, even if some of you think that you're lost" (Michael O. Rabin, höchstwahrscheinlich über einen anderen Beweis sprechend).



► Vorlesungsfolien zum Download: https://iccl.inf.tu-dresden.de/web/FS... (4. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: https://iccl.inf.tu-dresden.de/web/Fo...
► Fehler gefunden? Issues melden auf github: https://github.com/knowsys/FormaleSys...

Lizenz: Creative Commons CC-BY-SA, relevante Bildrechte siehe Video.