Nichtdeterministische endliche Automaten und der Satz von Scott-Rabin (Theoretische Informatik)

Nichtdeterministische Automaten (NFA) dürfen sich "aussuchen", was sie machen. Sie akzeptieren nach dem Satz von Scott-Rabin zwar nicht mehr Sprachen als ihre deterministischen Gegenstücke, sind aber oft einfacher zu handhaben.
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/ti-skript.pdf
* KORREKTUREN: weitz.de/corr/Vqs_FM_qQCw
* Das Video im Playlist-Kontext: weitz.de/y/Vqs_FM_qQCw?list=PL...
* Liste aller Videos: weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* "FAQ": weitz.de/youtube.html
00:00 Definition NFA
05:24 Beispiel für einen NFA
09:42 Der Satz von Scott-Rabin
15:36 Beispiel für die Potenzmengenkonstruktion
22:04 Reguläre Grammatiken und endliche Automaten
23:49 Alternativen in der Fachliteratur
28:13 Konkatenation von regulären Sprachen
31:40 Kleenesche Hülle von regulären Sprachen
Corrections:
18:50 Bitte beachten Sie die Korrekturhinweise in der Videobeschreibung.