Dieser Bereich beschäftigt sich mit der theoretischen Konstruktion sog. endlicher Automaten. Die Grundidee findet sich bei vielen Automaten im Alltag wieder: Durch eine Eingabe (z.B. Tastendruck, Münzeinwurf) reagiert der Automat und ändert nach einem festen Schema seinen Zustand, reagiert also in gewisser Weise auf die Benutzereingabe. Diese Grundidee wird genutzt, um sog. endliche Automaten sowie zugehörige Zustandsgraphen zu entwerfen, die für vorgegebene Aufgabenstellungen eine Lösung bieten. Solche Automaten lassen sich oft unmittelbar in ein Schaltnetzt umsetzen, wodurch eine enge Verknüpfung mit der technischen Informatik gegeben ist. Auf einer etwas abstrakteren Ebene kann man Automaten auch als Werkzeuge verstehen, die in der Lage sind, bestimmte Sprachen formal zu untersuchen und Wörter aus der Sprache auf Korrektheit zu prüfen (Syntaxprüfung). Die nach sehr eingeschränkten Regeln arbeitenden endlichen Automaten erkennen „nur“ vergleichsweise einfache Sprachen mit wenigen Regeln. Jede Sprache kann auch durch eine zugehörige Grammatik, also entsprechende „Konstruktionsregeln“ erzeugt werden. Auf erhöhtem Niveau werden auch komplexere Sprachen und Problemstellungen untersucht, die sich nicht mehr durch endliche Automaten lösen lassen. Hier werden dann auch Kellerautomaten und Turingmaschinen betrachtet.