Automatentheorie und Formale Sprachen [VAuFS]

Sommersemester 2006
Lehrstuhl für Informatik II
Grundstudium

Termine

Art	Termine	Beginn	Veranstalter
V3	Di 11:45 - 13:15 Gr	4. April	Katoen
	Fr 10:45 - 11:30 Gr	7. April
Ü1	Fr 10:00 - 10:45 Gr	7. April	Katoen, Bohnenkamp

Veranstalter

Vorlesung		Übungen
Prof. Dr. J-P Katoen		Dr. Henrik Bohnenkamp
Raum 4214		Raum 4210
Tel.: 80-21201		Tel.: 80-21203

Neuigkeiten

Ablauf der Vorlesung

Die Vorlesung hat 3+1 SWS. Dennoch werden wir 2-stündige Übungen anbieten, eine pro Woche, betreut von studentischen Tutoren. Die +1 Übungsstunde wird als Hörsaal-Fragestunde benutzt. Da es sehr ineffizient ist, eine einstündige Vorlesung vorzubereiten und zu halten, wird in der Regel am Freitagstermin eine zweistündige Vorlesung mit einer zweistündigen Fragestunde abwechseln. Es gibt Ausnahmen von dieser Regel, darum hier eine Vorläufige Liste von Terminen und Veranstaltungen (V = Vorlesung, FS=Fragestunde):

Termin	Art		Termin	Art
Di 4.4. 11:45--13:15	V		Fr 7. 4. 10:00--11:30	V
Di 11.4. 11:45--13:15	V		Fr 14.4.	--(Karfreitag)
Di 18.4.	-- (Fachschaftsvollversammlung)		Fr 21. 4. 10:00--11:30	V
Di 25.4. 11:45--13:15	V		Fr-- --28. 4. 10:00--11:30	V (Achtung, Änderung!)
Di 2.5. 11:45--13:15	V (Achtung, Änderung der Änderung!)		Fr 5. 5. 10:00--11:30	V
Di 9.5. 11:45--13:15	FS		Fr 12. 5. 10:00--11:30	V
Di 16.5. 11:45--13:15	V		Fr 19. 5. 10:00--11:30	V
Di 23.5. 11:45--13:15	V		Fr 26. 5. 10:00--11:30	FS
Di 30.5. 11:45--13:15	V		Fr 2. 6. 10:00--11:30	Testklausur
Di 6.6. 11:45--13:15	Pfingstwoche		Fr 9. 6. 10:00--11:30	Pfingstwoche
Di 13.6. 11:45--13:15	Besprechung Testklausur		Fr 16. 6. 10:00--11:30	V
Di 20.6. 11:45--13:15	V		Fr 23. 6. 10:00--11:30	V
Di 27.6. 11:45--13:15	V (Änderung)		Fr 30. 6. 10:00--11:30	V
Di 4. 7. 11:45--13:15	FS		Fr 7. 7. 10:00--11:30	V
Di 11. 7. 11:45--13:15	V		Fr -- --14. 7. 10:00--11:30	keine Veranstaltung

Tutorien

Achtung, Raumänderung: Die Übung von Benedikt Westermann (Di, 15:30, 6019) wird auf den Montag, 11:45, AH 1 verschoben. Die Leute, die sich für den Dienstagstermin angemeldet haben, mögen bitte in die Übung von Evamarie Storch gehen.

Nr	Wann?	Wo?	Wer?		Nr	Wann?	Wo?	Wer?
1	Mo, 11:45--13:15	AH 2	Thomas Kesselheim		4	Di, 14:00 -- 15:30	5056	Evamarie Storch
6	Mo, 11:45 -- 13:15	AH 1	Benedikt Westermann		5	Di, 15:30 -- 17:00	5054	entfällt
3	Di, 8:15--9:45	AH 1	Evamarie Storch		8	Di, 15:45 -- 17:15	AH 2	Roman Rabinovich
2	Di, 8:15--9:45	5055	Christian Lücking		7	Di, 15:45 -- 17:15	5052	Andreas Röll

Es ist geplant, ein Tutorium speziell den Studierenden der Technik-Kommunikation zu widmen. Wir sehen dafür den Dienstags um 14:00 vor. Es ist natürlich jeder/m freigestellt, sich dennoch für eine andere Gruppe anzumelden.

Zur Anmeldung.

Übungsblätter

Nr
1	PS	PDF
2	PS	PDF
3	PS	PDF
4	PS	PDF
5	PS	PDF
6	PS	PDF
7	PS	PDF
8	PS	PDF
9	PS	PDF
10	PS	PDF
11	PS	PDF
12	PS	PDF

Klausuren

Testklausur incl. Lösungen	PDF

Diplom-Vorprüfung

Die Diplom-Vorprüfung (2-stündige Klausur) findet am 5. September 2006, irgendwann zwischen 8 und 12 Uhr
statt. Informationen zu den Austragungsorten wird noch bekannt gegeben, siehe aber auch im Campus-System.

Parallel zu der VD-Klausur werden wir eine Scheinklausur stellen, die von all denen, die einen Schein benötigen, geschrieben werden muss.

Erwerb eines Übungsscheins

• Hausaufgaben: 50% der erreichbaren Punkte
• Scheinklausur: muss natürlich bestanden werden.

Newsgroup/Forum

Die ATFS-Newsgroup bietet ein Forum zum gegenseitigen Informationsaustausch. Hilfe lässt sich vielleicht auch im infostudium Webforum finden.

Inhalt

Die Beschreibung syntaktischer Strukturen durch reguläre Ausdrücke und kontextfreie Grammatiken sowie ihre effiziente Erkennung durch endliche Automaten und Kellerautomaten bilden eine wichtige Grundlage für die Übersetzung von Programmiersprachen und die Konstruktion zahlreicher Software-Werkzeuge.

Im Unterschied zur Vorlesung "Berechenbarkeit und Komplexität" steht nicht die Berechnung von Funktionen, sondern die Erzeugung und Erkennung formaler Sprachen im Vordergrund. Die größte Klasse solcher effektiv beschreibbaren Sprachen stellen die von Turing-Maschinen erkennbaren, rekursiv aufzählbaren Sprachen dar.

Themenübersicht:

• Reguläre Ausdrücke und endliche Automaten
• Kontextfreie Grammatiken und Kellerautomaten
• Turingmaschinen, Aufzählbarkeit und Entscheidbarkeit

Der genaue Inhalt der Vorlesung wird sich an den Vorlesungen der vergangenen Jahre orientieren.

Folien und Handouts

Die Vorlesung wird an der Tafel entwickelt. Insofern werden hier nur ausnahmsweise Folien für Beispiele o.ä. veröffentlicht.

Zur Vorlesung am 12. 5. 2006

• Zur Brüggemann-Klein/Wood-Konstruktion
• Zu Jaffe's Pumping-Lemma

Zur Vorlesung am 30. 5. 2006

• Algorithmen zur Chomsky-NF-Konstruktion

JFLAP

JFLAP ist eine Suite von graphischen Tools "which can be used as an aid in learning the basic concepts of Formal Languages and Automata Theory." Diese Tools werden gelegentlich in der Vorlesung zur Veranschaulichung eingesetzt. JFLAP ist frei erhältlich und, da in Java programmiert, unabhängig von der Plattform. Ein Buch zu JFLAP is kürzlich erschienen (s.u.). Dieses wird demnächst im Handapparat zur Verfügung stehen.

Literatur

• A. Asteroth, C. Baier, Theoretische Informatik, Pearson Studium, 2002
• J.E. Hopcroft, R. Motwani, J.D. Ullmann: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001
• I. Wegener, Theoretische Informatik, Teubner, 2. Auflage, 1999
• Susan H. Rodger and Thomas W. Finley, JFLAP: An Interactive Formal Languages and Automata Package, Jones & Bartlett Publishers, 2006.