Endliche Automaten sind ein nützliches und weit verbreitetes Modell für
viele wichtige Arten von Hardware und Software. Dieses Modell wird zusammen mit
damit zusammenhängenden Konzepten wie Grammatiken oder regulären Ausdrücken
im Modul Grundlagen der Theoretischen Informatik (GTI) ausführlich behandelt.

In diesem Seminar werden wir uns hauptsächlich mit Erweiterungen von endlichen
Automaten beschäftigen, welche es uns erlauben, komplexere Systeme zu modellieren.
So können beispielsweise probabilistische Systeme durch probabilistische Automaten
beschrieben werden, welche nichtdeterministische endliche Automaten durch
eine Übergangsfunktion erweitern, oder Realzeitsysteme durch sogenannte timed automata,
welche endliche Automaten um eine endliche Menge von Uhren erweitern.

Eine zentrale Frage ist dabei häufig die Entscheidbarkeit, das bedeutet die Frage danach,
ob ein Computer in endlicher Zeit entscheiden kann, ob ein gegebenes Wort
vom Automaten akzeptiert wird. Falls das der Fall ist, interessiert uns auch die Komplexität
dieser Entscheidung; der Rechenaufwand im Vergleich zur Größe des Automaten.