Mitteilungen
- Die Prüfung findet am 12.03. um 11:30 Uhr im Faraday-Hörsaal statt.
- In Vorbereitung auf die Prüfung findet am 09.03. um 14:00 Uhr im Z 2086 eine letzte Konsultation statt.
- Die Klausureinsicht von AFS findet am 30.04. zwischen 10:30 - 13:00 Uhr im Raum Z1050 statt. Bitte bringen Sie Ihren Studierendenausweis mit. Wir weisen im Voraus darauf hin, dass das Aufnehmen von Fotos, Videos, o. Ä. nicht gestattet ist.
- Ab sofort findet die Vorlesung im Humboldt-Hörsaal statt, die Zeiten bleiben unverändert.
- Um bei Interesse aktuelle Informationen (Raumänderungen, korrigierte Übungsaufgaben, ...) zu erhalten, tragen Sie sich bitte im Moodle-Kurs ein.
- Einige der Übungsaufgaben sind als Bonusaufgaben gekennzeichnet. Ihre handschriftliche Lösung dieser Aufgaben geben Sie bitte bis zum auf dem Übungsblatt verzeichneten Zeitpunkt (üblicherweise Montag der geraden Woche 15 Uhr) im Briefkasten vor dem Raum Z 1047 oder am Anfang der Montag-Übung ab. Diese werden korrigiert, die dabei erhaltenen Punkte werden in Bonuspunkte für die Klausur umgerechnet. Die korrigierten Lösungen werden in den Übungen zurückgegeben.
- Zu jedem 2. Übungstermin wird ein kurzer Test geschrieben, in dem Definitionen, Sätze etc. abgefragt werden. Auch die hierbei erhaltenen Punkte werden in Bonuspunkte für die Klausur umgerechnet.
- Neben den Übungen bieten wir auch regelmäßig eine Konsultation (Donnerstag der ungeraden Woche, 11 Uhr, Z 2073) an. In dieser werden ausschließlich von Ihnen vorgebrachte Themen besprochen.
Materialien
- Die Materialien zur Vorlesung oder zur Übung werden im Laufe des Semesters aktualisiert.
Vorlesungen
- Vorlesung 01 (16.10.): Vorbemerkungen und Grundbegriffe
Folien - Vorlesung 02 (23.10.): Grammatiken und die Chomsky-Hierarchie
Folien, Mitschnitt - Vorlesung 03 (30.10.): Endliche Automaten und rechtslineare Sprachen (1)
Folien, Mitschnitt - Vorlesung 04 (06.11.): Endliche Automaten und rechtslineare Sprachen (2)
Abschlußeigenschaften
Folien, Mitschnitt - Vorlesung 05 (13.11.): Reguläre Ausdrücke und rechtslineare Sprachen
Folien - Vorlesung 06 (20.11.): Nicht-reguläre Sprachen (1): Das Pumping-Lemma
Folien (beachten Sie die Änderung auf Folie 3!), Mitschnitt - Vorlesung 07 (27.11.): Nicht-reguläre Sprachen (2): Der Satz von Myhill-Nerode; Der minimale DFA (1): Existenz
Folien, Mitschnitt - Vorlesung 08 (04.12.): Der minimale DFA (2): Berechnung; Algorithmen für reguläre Sprachen
Folien, Mitschnitt - Vorlesung 09 (11.12.): Kontextfreie Sprachen und Ableitungsbäume
Folien, Mitschnitt - Vorlesung 10 (18.12.): Polynomielle Lösung des Wortproblems: Chomsky-NF und CYK-Algorithmus
Folien - Vorlesung 11 (08.01.): Kellerautomaten und Greibach-Normalform
Folien, Mitschnitt - Vorlesung 12 (15.01.): Kellerautomaten und kontextfreie Sprachen
Folien - Vorlesung 13 (22.01.): Abschlußeigenschaften und Nicht-Abschluß: Das Pumping-Lemma
Folien - Vorlesung 14 (29.01.): Kellerautomaten mit Endzuständen und deterministische Kellerautomaten
Folien, Mitschnitt - Vorlesung 15 (05.02.): Algorithmen für kontextfreie Sprachen
Folien, Mitschnitt
Übungen
- Übung 01* (27.10., 29.10.): Sprachen und Grammatiken
Aufgabenblatt - Übung 02 (10.11., 12.11.): Grammatiken und endliche Automaten
Aufgabenblatt - Übung 03* (24.11., 26.11.): Reguläre Ausdrücke und das
Pumping-Lemma
Aufgabenblatt - Übung 04 (08.12., 10.12.): Minimierung und Myhill-Nerode
Aufgabenblatt - Übung 05* (05.01., 07.01.): Kontextfreie Grammatiken und der
CYK-Algorithmus
Aufgabenblatt - Übung 06 (19.01., 21.01.): PDAs und Greibach-Normalform
Aufgabenblatt - Übung 07* (02.02., 04.02.): Abschlusseigenschaften und das
Pumping-Lemma für kontextfreie Sprachen
Aufgabenblatt
- An Übungen, die mit einem (*) markiert sind, findet ein kurzer Test statt
Allgemeine Informationen zum Kurs
Termine
- Vorlesung: (Prof. Dr. Dietrich Kuske)
Donnerstag, 09:00 - 10:30 Uhr, HU-Hs (Humboldtbau)
- Übungen: (M. Sc. Lisa Barthel)
Montag (G), 15:00 - 16:30 Uhr, Sr K 2026 (Kirchhoffbau)
Mittwoch (G), 09:00 - 10:30 Uhr, Sr HU 211/212 (Humboldtbau) - Konsultation: (M. Sc. Lisa Barthel)
Donnerstag (U), 11:00 - 12:30 Uhr, Z 2073 (Zusebau) - Konsultation zur Klausur: (M. Sc. Lisa Barthel)
Montag (09.03.26), 14:00 - 15:30 Uhr, Z 2086 (Zusebau)
