Formale Systeme, Automaten, Prozesse

 

Vorlesung im Sommersemester 2018

 
Potenzmengenkonstruktion Urheberrecht: M. Ritzert

Ansprechpartner

Telefon

work
+49 241 80 21702

E-Mail

E-Mail
 

Termine

Vorlesung
Mo, 10:15 - 11:45 Uhr (Grüner Hörsaal AM)
Di, 10:15 - 111:45 Uhr (Roter Hörsaal AM)

Übung
Mo, 18:15 - 19:45 Uhr (OTTO FUCHS-Hörsaal H03)

 
 

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 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

Martin Grohe