Automatentheorie und formale Sprachen (SS2005)

Peter Rossmanith

Pflichtvorlesung im Grundstudium
3+1 Semesterwochenstunden
zweistündige Tutorübungen

Zeit und Ort

Dienstags	11:45-13:15	Hörsaal Gr	(Vorlesung)
Freitags	10:00-10:45	Hörsaal Gr	(Zentralübung)
Freitags	10:45-11:30	Hörsaal Gr	(Vorlesung)

ATFS-Klausur vom 13.09.2005: Die mündlichen Nachprüfungen sollen in der Woche vom 7. bis 11. November stattfinden. Bitte melden Sie sich, sofern die Prüfungsordnung Ihnen das Recht auf eine mündliche Nachprüfung gewährt, bei Daniel Mölle wegen eines Termins per E-Mail.

Die Klausurergebnisse stehen fest.

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

Übung

Die Übungen beginnen in der zweiten Vorlesungswoche. Bitte beachten Sie, daß wir nicht alle der im Campus-System genannten Übungen anbieten können.

Tag	Zeit	Raum	Tutor
Mo	08:15-09:45	SG 12	Zimmer
Mo	10:00-11:30	AH II	Wright
Mo	11:45-13:15	AH I	Lambertz
Mo	14:00-15:30	SG 203	Vontin
Di	15:45-17:15	5052	Rabinovich
Di	15:45-17:15	AH II	Langer
Mi	11:45-13:15	5052	Drobny

Zusätzlich bieten wir eine besondere Übungsgruppe an, die in Inhalt, Aufgaben und Schwierigkeit über den Vorlesungsstoff hinausgeht. Diese Spezialgruppe ist für besonders interessierte Studierende gedacht und findet am Montag um 11:45 Uhr im Raum 5052 statt.

Literatur

J.E. Hopcroft, R. Motwani, J.D. Ullmann: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001.

Dieses Buch gibt es auch auf Deutsch unter dem Titel Einführung in der Automatentheorie, Formale Sprachen und Komplexitätstheorie.