Kontextsensitive und rekursiv aufzählbare Sprachen (Theoretische Informatik)

Welche Automatentypen gehören zu Typ-0- und Typ-1-Sprachen? Was sind nichtdeterministische Turingmaschinen und was bedeutet Akzeptanz bei Turingmaschinen? Was sind linear beschränkte Turingmaschinen? Außerdem der Satz von Immerman und Szelepcsényi und das ungelöste erste LBA-Problem.
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/ti-skript.pdf
* KORREKTUREN: weitz.de/corr/BDdZ1f77Les
* Das Video im Playlist-Kontext: weitz.de/y/BDdZ1f77Les?list=PL...
* Liste aller Videos: weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* "FAQ": weitz.de/youtube.html
00:00 Akzeptanz bei Turingmaschinen
01:41 Nichtdeterministische Turingmaschinen
05:45 Äquivalenz von deterministischen und nichtdeterministischen Turingmaschinen
11:29 Kontextsensitive Grammatiken
15:43 Die Chomsky-Hierarchie
19:28 Rekursiv aufzählbare Sprachen und Turingmaschinen
34:23 Linear beschränkte Turingmaschinen und kontextsensitive Sprachen
43:46 Unterschiede zwischen kontextfreien und kontextsensitiven Sprachen
52:17 Abschlusseigenschaften kontextsensitiver Sprachen
Corrections:
37:30 Bitte beachten Sie die Korrekturhinweise in der Videobeschreibung.