16: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 29.01.2019 Theoretische Grundlagen der Informatik, Vorlesung, WS18/19

16 |
0:00:00 Start
0:00:32 Letzte Vorlesung
0:02:51 Wdh.: Greibach-Normalform, Kellerautomat
0:06:32 Beispiel - Greibach-Normalform
0:12:41 Beispiel - Kellerautomat
0:17:47 Beweis: Greibach-Normalform -NPDA
0:26:14 Übersicht
0:27:41 Beweis:NPDA - kontextfreie Grammatik
0:51:16 Exkurs
0:55:11 Zwischenfazit zu kontextfreien Grammatiken
0:57:12 Unentschedbare Probleme für kontextfreie Grammatiken
1:00:05 Das Post'sche Korrespondenzproblem
1:01:10 Beweis
1:06:43 Eindeutigkeit von kontextfreien Grammatiken
1:09:01 Sprache der korrekten Rechenwege
1:27:34 Zusammenfassung Chomsky-Hierarchie