Einführung in die
Berechenbarkeit und Formale Sprachen (WS 2002/03)

Inhalt

Berechenbarkeit

• Turingmaschinen
• entscheidbare und rekursiv aufzählbare Sprachen
• nicht enscheidbare Probleme
• Halteproblem
• nicht rekursiv aufzählbare Probleme

Formale Sprachen

• reguläre Sprachen, reguläre Grammatiken
• deterministische, nicht-deterministische Automaten
• reguläre Ausdrücke
• Äquivalenzsatz
• Pumping Lemma
• kontexfreie Sprachen, kontextfreie Grammatiken
• Kellerautomaten
• Chomsky Normalform, Äquivalenzsatz
• CYK-Algorithmus

Termine

Vorlesung:
Di 11-13, Raum C1
(erste Vorlesung am 15.10.02)

Zentralübung:
Mo 14-16, Raum C1. Die nächste Zentralübung ist am 13.01.03.

Übungen:

Ab dem 06.02. finden keine Tutorien mehr statt.

Die Übungen finden 2-wöchentlich beginnend am 17.10.02 statt. In der ersten Semesterwoche beginnen die Übungsgruppen Ü1,Ü3,Ü5,Ü7,Ü9,Ü11. Dies sind die im Vorlesungsverzeichnis mit einem "g" gekennzeichneten Gruppen.

Nummer	Zeit	Raum	Betreuer
Ü1/Ü2	Mo 09:00 - 11:00	D1.338	Ulrich Hoppe
Ü3/Ü4	Mo 11:00 - 13:00	D1.320	Karsten Tiemann
Ü5/Ü6	Mo 11:00 - 13:00	E2.310	Christian Soltenborn
Ü7/Ü8	Fr 09:00 - 11:00	D1.328	Birgitta Fricke
Ü9	Do 14:00 - 16:00	E2.310	Alex May
Ü10	Do 14:00 - 16:00	E2.310	Marcel Ackermann
Ü11	Do 16:00 - 18:00	E2.310	Alex May
Ü12	Do 16:00 - 18:00	E2.310	Marcel Ackermann

Skript

Im Laufe des Semesters wird an dieser Stelle ein Skript erscheinen. Dieses Skript kann jedoch das Lesen von Lehrbüchern nicht ersetzen.

• Turingmaschinen als PS-File und als PDF-File
• Programmiertechniken und Mehrband DTMs (verbesserte Version) als PS-File und als PDF-File
• RAMs und Turingmaschinen als PS-File und als PDF-File
• Universelle Turingmaschinen als PS-File und als PDF-File
• Unentscheidbare Sprachen und Reduktionen als PS-File und als PDF-File (leicht geänderte Versionen)
• Grammatiken als PS-File und als PDF-File
• Deterministische endliche Automaten als PS-File und als PDF-File
• Nichtdeterministische endliche Automaten als PS-File und als PDF-File
• Äquivalenz- und Minimalautomaten als PS-File und als PDF-File
• Pumping Lemma und reguläre Ausdrücke als PS-File und als PDF-File
• Kontextfreie Grammatiken und Kellerautomaten als PS-File und als PDF-File

Übungen

An dieser Stelle erscheinen im Laufe des Semesters die Übungen und die Musterlösungen.

Übung	Musterlösung
1.Übung	1.Musterlösung
2.Übung	2.Musterlösung
3.Übung	3.Musterlösung
4.Übung	4.Musterlösung
5.Übung	5.Musterlösung
6.Übung	6.Musterlösung
7.Übung	7.Musterlösung

Jetzt das Ganze noch einmal in PDF.

Übung	Musterlösung
1.Übung	1.Musterlösung
2.Übung	2.Musterlösung
3.Übung	3.Musterlösung
4.Übung	4.Musterlösung
5.Übung	5.Musterlösung
6.Übung	6.Musterlösung
7.Übung	7.Musterlösung

Prüfung

Im Anschluß an die Vorlesung "Komplexität und Algorithmen" im kommenden Sommersemester wird es eine Prüfung über beide Vorlesungen geben. Die Prüfung erfolgt durch eine Klausur. Wenn Sie aktiv in den Übungen mitarbeiten, können Sie Ihre Klausurnote wie folgt verbessern:

• Erreichen Sie mindestens 50% der Punkte der Übungen, so verbessert sich die Note um 1/3.
• Erreichen Sie mindestens 75% der Punkte der Übungen, so verbessert sich die Note um 2/3.

WICHTIG: Eine Verbesserung der Klausurnote 5 (nicht bestanden) ist nicht möglich.

Literatur

• Introduction to the Theory of Computation, Michael Sipser, PWS, 1997.
• Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addsion Wesley, 2. Auflage 2001.
• Elements of the Theory of Computation, Harry R. Lewis, Christos H. Papadimitriou, Prentice Hall, 2. Auflage 1998.
• Theory of Computing - A Gentle Introduction, Efim Kinber, Carl Smith, Prentice Hall, 2001.
• Theoretische Informatk - kurzgefaßt, Uwe Schöning, Spektrum, akad. Verlag, Heidelberg, 3. Auflage 1997.
• Theoretische Informatik - Eine algorithmenorientierte Einführung, Ingo Wegener, Teubner, 1993.

Die Vorlesung wird sich hauptsächlich an den drei zuerst genannten Büchern orientieren. Besonders empfohlen wird das Buch von M.Sipser.

Gruppenarbeit:

Wir fordern Sie ausdrücklich auf, in kleinen Gruppen (3-4 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg (und den Spaß am Studieren) ist das sehr förderlich. Sie dürfen Ihre Übungen auch in solchen Gruppen abgeben.