Grundlagen der Informatik 2, Vorlesung 23: Reguläre Sprachen

Die am stärksten eingeschränkte Sprachklasse in der Chomsky-Hierarchie sind die regulären Sprachen. Im Gegenzug erweisen sich die regulären Sprachen als besonders günstig was Entscheidungsprobleme anbelangt. Alle wichtigen Entscheidungsfragen für reguläre Sprachen sind entscheidbar, die meisten sogar effizient. Darüber hinaus sind reguläre Sprachen auch äußerst robust: Unter Zuhilfenahme des Akzeptormodells des deterministischen endlichen Automaten (DFA) zeigen wir, dass reguläre Sprachen unter vielen Operatoren, beispielsweise Schnitt, Komplement und Kleene-Stern, abgeschlossen sind. Wir schließen die Vorlesung, indem wir ein Kriterium kennenlernen, mit dem für eine beliebige Sprache untersucht werden kann, ob sie regulär ist: Die Myhill-Nerode-Äquivalenz.