Logic and
Theory of
Discrete Systems

Informatik 7

Prof. Martin Grohe
Prof. Wolfgang Thomas

Formale Systeme, Automaten, Prozesse

Vorlesung im Sommersemester 2015

Diese Vorlesung wird auf deutsch gehalten. Es gibt einen L²P-Lernraum sowie ein Übungssystem zu dieser Veranstaltung. Die Assistenten sind unter fosap (ät) automata.rwth-aachen.de zu erreichen. 

ArtTermine/OrtBeginnVeranstalter 
V3 Mo 10:15–11:45, Roter Hörsaal AM
Di 10:15–11:45, Roter Hörsaal AM
Mo, 13. April Thomas Campus-Link
Ü2 Fr 16:15–17:45, Fo 2 (Hörsaalübung) Fr,  17. April Thomas, Winter, Frickenschmidt, Frohn Campus-Link
Tutorium Es werden Kleingruppenübungen zu unterschiedlichen Terminen angeboten. Details werden in der Vorlesung bekanntgegeben.      

Inhalt

Automaten und Grammatiken sind die Standardwerkzeuge des Informatikers zur Modellierung und Transformation von Systemen und Prozessen. Außerdem bilden sie die Basis für die Definition und Übersetzung von Programmiersprachen, ebenso wie für die Algorithmik über Zeichenreihen (Pattern-Matching).

Im Zentrum dieser Grundvorlesung steht zunächst das Modell des endlichen Automaten, dessen Verhaltensbeschreibung durch reguläre Ausdrücke und die Frage, welche Informatik-Systeme man auf diese Weise modellieren kann. Im zweiten Teil der Vorlesung geht es um die Spezifikation von Daten durch Grammatiken, ihre Erkennung durch Kellerautomaten und Verbindungen zu anderen Formalismen. Es werden vor allem algorithmische Fragen untersucht, zum Beispiel, ob die Äquivalenz zwischen Automaten bzw. Grammatiken entscheidbar ist (und wenn ja, wie effizient dies geht).