Formale Systeme, Automaten, Prozesse

 

Vorlesung im Sommersemester 2015

Kontakt

Telefon

work
+49 241 80 21710

E-Mail

E-Mail
 
 

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, dem Pattern-Matching.

Im Zentrum dieser Grundvorlesung steht zunächst das Modell des endlichen Automaten, dessen Verhaltensbeschreibung durch reguläre Ausdrücke beschrieben werden kann 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.

 

Organisation

Vortragssprache in Deutsch.

Dozent

Wolfgang Thomas