Institut für Informatik

Universität Leipzig Institut für Informatik Automaten und Sprachen Karin Quaas

Wintersemester 2010/11
Übungen zu Automaten und Sprachen

Termine

Vorlesung am Montag 13.15-14.45, HS 10.

Übungen am Dienstag bzw. Mittwoch 9.15-10.45, SG 3-12 bzw. 3-10.

Die Ergebnisse der Wiederholungsklausur vom 6.4.2011 finden Sie hier. Wenn Sie die Klausur einsehen wollen, setzen Sie sich bitte per Email mit mir in Verbindung.

Die Ergebnisse der Klausur vom 5.2.2011 finden Sie hier.

Teilnehmer: 62, Bestanden: 53, Nicht bestanden: 9.

Note	Anzahl
1	7
2	10
3	21
4	15
5	9

Übungsblätter

Hinweis zu Serie 6: Ein Kellerautomat M=(Q,&Sigma,&Gamma,&delta,p,Z,F) mit Finalzuständen heisst deterministisch falls |&delta(q,a,A)| + |&delta(q,&epsilon,A)| <= 1 für alle q in Q, a in &Sigma, A in &Gamma .

Hinweis zu Serie 4: Die in der Übung am 30.11. besprochene Grammatik ist vom Typ 2. Das Startsymbol S darf auf der rechten Seite einer Regel vorkommen. Hinweis 2: Der Begriff der Eindeutigkeit in Aufgabe 5 bezieht sich auf die Anzahl der Ableitungsbäume in der Grammatik!

Die Auswertung aller Übungsblätter ergab folgenden Punktestand. Zur Prüfung zugelassen sind alle Studenten, die mindestens 50% der Gesamtpunktzahl erreicht haben. Melden Sie sich zur Prüfung bis spätestens 29.1.2011 hier an.

Autotool

Bitte schreiben Sie sich online ab 11.10.2010 9.00 Uhr in die Übungsgruppen im Autotool ein, welches Sie auch zur Bearbeitung einiger Hausaufgaben verwenden werden. Eine Dokumentation des Autotools, im Besonderen zum Anlegen eines Benutzerkontos und Einschreiben in die Übungsgruppen finden Sie hier: Autotool-Doku.

Literatur

J.E.Hopcroft, R.Motwani, J.D.Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, 2002.

U.Schöning: Theoretische Informatik - kurzgefasst. Spektrum, 2001.

I.Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner, 1999.

I.Wegener: Kompendium Theoretische Informatik. Eine Ideensammlung. Teubner, 1996.