Grundlagen der Informatik 2: Einführung in Kontextfreie Sprachen 🧠

Reguläre Sprachen haben sich als eine äußerst angenehme Sprachklasse erwiesen, die sich algorithmisch einfach handhaben lassen. Allerdings sind die Einschränkungen nicht unerheblich - reguläre Sprachen erlauben beispielsweise nicht einmal unbeschränktes Zählen. Wenn eine Fragestellung mit regulären Sprachen nicht gehandhabt werden kann, ist der nächstbeste Kandidat eine kontextfreie Sprache. Wir lernen den CYK-Algorithmus kennen, der es erlaubt, das Wortproblem für kontextfreie Sprachen effizient zu entscheiden. Leider gibt aber nicht für alle Fragestellungen zu kontextfreien Sprachen einen effizienten Algorithmus. Wir schließen die Vorlesung mit einer Diskussion des Pumping Lemmas für kontextfreie Sprachen.