Grundlagen der Informatik 2, Vorlesung 22: Die Chomsky-Hierarchie

Zahlreiche Probleme sind unentscheidbar, viele weitere wahrscheinlich nicht effizient entscheidbar. Ist also alle Hoffnung für einen großen Teil der interessanten Fragestellungen verloren? Eine Lösung um dieser Schwierigkeit zu begegnern ist, die Mächtigkeit der Modellierungssprache zu beschränken. Die Chomsky-Hierarchie erlaubt es, drei Stufen der Modelleinschränkungen zu definieren, die sukzessive mehr Fragestellungen entscheidbar werden lassen. In dieser Vorlesung werden wir uns an die Chomsky-Hierarchie herantasten und formale Grammatiken als Modellierungswerkzeug kennenlernen.