Kontextfreie Sprachen: Chomsky-Normalform und Pumping-Lemma (Theoretische Informatik)

Durch die Chomsky-Normalform wird jeder Ableitungsbaum zu einem Binärbaum. Das liefert ein Pumping-Lemma für kontextfreie Sprachen und wir lernen eine Sprache kennen, die nicht kontextfrei ist. Außerdem geht es wieder um Abschlusseigenschaften: Vereinigung, Konkatenation, kleenesche Hülle, anders als bei reguläre Sprachen aber nicht Durchschnitt und Komplement.
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/ti-skript.pdf
* Das Video im Playlist-Kontext: weitz.de/y/e5-hNhM7h_8?list=PL...
* Liste aller Videos: weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* "FAQ": weitz.de/youtube.html
00:00 Kontextfreie Grammatiken
05:39 Chomsky-Normalform
09:55 Umwandlung in Chomsky-Normalform
21:09 Binärbäume
23:11 Pumping-Lemma für kontextfreie Sprachen
32:57 Abschlusseigenschaften kontextfreier Sprachen