Formale Systeme
Formale Systeme
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) im WS 2025
Dozent
Tutor
- Stephan Mennicke
- Stefan Borgwardt
- Anton Claußnitzer
- Florens Förster
- Lukas Gerlach
- Anna Hornschild
- Cornelius Lübke
- Maximilian Marx
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Klausur
Vorlesungsreihe
Die Lehrveranstaltung Formale Systeme vermittelt eine Einleitung in die Gebiete der formalen Sprachen, Automatentheorie und Berechenbarkeit. Dies beinhaltet einige der wichtigsten Grundlagen der Informatik, wie z.B. reguläre Ausdrücke, formale Grammatiken sowie grundlegende Begriffe der Berechenbarkeits- und Komplexitätstheorie. Damit bildet die Vorlesung die Grundlage für viele vertiefende Vorlesungen.
Vorlesungen
Die Vorlesungstermine sind
Die erste Vorlesung findet am Montag, dem 13. Oktober 2025 statt.
Übungen
Der Übungsbetrieb startet am 20. Oktober 2025 zu Ihren jeweiligen Terminen in den angegebenen Räumen statt. Die Übungsblätter können in der Spalte der jeweiligen Übung unter Termine und Unterlagen heruntergeladen werden. Eine vorherige Einschreibung in die angebotenen Übungstermine ist verpflichtend bevor Sie an der Übungsgruppe teilnehmen. Welche Übungstermine wir anbieten, geben wir rechtzeitig bekannt. Die Einschreibung wird am Montag, den 13.10.2025 um 15:00 Uhr freigeschalten:
Die Einschreibungen in die Übungsgruppen erfolgt über die OPAL-Seite der Lehrveranstaltung.
Unterlagen
Die vollständigen Foliensätze zur Vorlesung erscheinen bis zur Woche der Vorlesung online (siehe Termine und Unterlagen). Weiterführende Literatur ist unter Literatur angegeben. Die Quellen der Vorlesungsfolien sind auf github verfügbar: https://github.com/knowsys/FormaleSysteme
Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von Creative Commons CC By 3.0 Deutschland genutzt, weitergegeben und modifiziert werden. Als Namensnennung ist folgende Angabe einzufügen:
(C) Markus Krötzsch, https://iccl.inf.tu-dresden.de/web/FS2025, CC BY 3.0 DE
Bildrechte können davon abweichen und sind gesondert angegeben. Die Foliensätze enthalten keinerlei Texte, die aus Werken entnommen sind, für welche die VG Wort Verwertungsrechte vertritt.
Besonderen Dank gilt allen Contributors, die Anmerkungen und Verbesserungen beigetragen haben: Daniel Borchmann, Maximilian Marx, Christian Lewe, David Tiede, Johannes (jhaye), Andrej Bereza, CniKKoR, Marcus Rossel, Max Haertwig, Sönke (eknoes), Benno Fünfstück, Julius Schmitt. (Stand März 2021; Ergänzungen sind willkommen.)
Kontakt
Zur Kommunikation unter Vorlesungsteilnehmern der TU Dresden steht ein Matrix-Kanal zur Verfügung.
Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/mkroetzsch/FormaleSysteme Alternativ können Hinweise zu Tippfehlern in den Vorlesungsfolien auch an die Mailingliste geschickt werden.
Persönliche Fragen können direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht über andere Kanäle gerichtet werden können. Allgemeine Fragen sollten Sie aber immer in geteilten Kanälen stellen, damit auch Ihre Kommilitoninnen und Kommilitonen davon profitieren (oder vielleicht sogar direkt helfen können).Allgemein sind die Vorlesungsfolien und Übungsunterlagen ausreichend detailliert für das Studium. Weitere Lehrmaterialien können dennoch hilfreich sein, um Details nachzuschlagen oder sich weiter im Thema zu vertiefen.
Formale Sprachen, Komplexität und Entscheidbarkeit
Lehrbücher
- Uwe Schöning: Theoretische Informatik -- kurz gefasst. Spektrum Akademischer Verlag.
- (deutschsprachiger Standardtext; in der Tat ziemlich kurz gefasst)
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit. Pearson Studium.
- (aus dem Englischen übertragenes Standardwerk; Original ev. besser)
- Michael Sipser: Introduction to the Theory of Computation. Cengage Learning.
- (Standardtext zu Sprachen und Berechnungskomplexität; leider nur auf Englisch)
Online verfügbare Skripte
Die Vorlesungen haben kleine Abweichungen von diesem Text, stimmen aber in vielen wichtigen Punkten überein.
Andere Scripte scheinen zurzeit nicht (mehr) online verfügbar zu sein. Hinweise zu weiteren Links auf sinnvolle Materialien sind willkommen.Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | Einleitung formale Sprachen | DS3, 13. Oktober 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Vorlesung | Grammatiken und die Chomsky-Hierarchie | DS4, 16. Oktober 2025 in HSZ/0003 | Datei 1, Datei 2 |
| Übung | Übungsblatt 1 | Datei | |
| Vorlesung | Endliche Automaten | DS3, 20. Oktober 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Vorlesung | Nichtdeterministische Automaten | DS4, 23. Oktober 2025 in HSZ/0003 | Datei 1, Datei 2 |
| Übung | Übungsblatt 2 | Datei | |
| Vorlesung | Abschlusseigenschaften regulärer Sprachen | DS3, 27. Oktober 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Vorlesung | Reguläre Ausdrücke (1) | DS4, 30. Oktober 2025 in HSZ/0003 | Datei 1, Datei 2 |
| Übung | Übungsblatt 3 | Datei | |
| Vorlesung | Reguläre Ausdrücke (2) | DS3, 3. November 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Entfällt | Interne Veranstaltung | DS4, 6. November 2025 in HSZ/0003 | |
| Übung | Übungsblatt 4 | Datei | |
| Vorlesung | Minimale Automaten (1) | DS3, 10. November 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Vorlesung | Minimale Automaten (2) | DS4, 13. November 2025 in HSZ/0003 | Datei 1, Datei 2 |
| Übung | Übungsblatt 5 | Datei | |
| Vorlesung | Grenzen regulärer Sprachen / Probleme für Automaten | DS3, 17. November 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Vorlesung | Von regulären zu kontextfreien Sprachen | DS4, 20. November 2025 in HSZ/0003 | Datei 1, Datei 2 |
| Übung | Übungsblatt 6 | Datei | |
| Vorlesung | Das Wortproblem für kontextfreie Sprachen | DS3, 24. November 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Vorlesung | Das Pumping Lemma kontextfreier Sprachen | DS4, 27. November 2025 in HSZ/0003 | Datei 1, Datei 2 |
| Übung | Übungsblatt 7 | Datei | |
| Vorlesung | Abschlusseigenschaften kontextfreier Sprachen | DS3, 1. Dezember 2025 in BAR/SCHÖ | Datei 1, Datei 2 |
| Vorlesung | Einleitung Kellerautomaten | DS4, 4. Dezember 2025 in HSZ/0003 | Datei 1, Datei 2 |
| Übung | Übungsblatt 8 | Datei | |
| Vorlesung | Kellerautomaten und CFGs | DS3, 8. Dezember 2025 in BAR/SCHÖ | |
| Vorlesung | Deterministische Sprachen / Entscheidungsprobleme | DS4, 11. Dezember 2025 in HSZ/0003 | |
| Vorlesung | Turingmaschinen | DS3, 15. Dezember 2025 in BAR/SCHÖ | |
| Konsultation | Repetitorium (1) | DS4, 18. Dezember 2025 in HSZ/0003 | |
| Vorlesung | Nichtdeterministische Turingmaschinen und Unentscheidbarkeit | DS3, 5. Januar 2026 in BAR/SCHÖ | |
| Vorlesung | Typ 0 und Typ 1 | DS4, 8. Januar 2026 in HSZ/0003 | |
| Vorlesung | Berechenbarkeit und Unentscheidbarkeit | DS3, 12. Januar 2026 in BAR/SCHÖ | |
| Vorlesung | WHILE und LOOP | DS4, 15. Januar 2026 in HSZ/0003 | |
| Vorlesung | Das Halteproblem und Reduktionen | DS3, 19. Januar 2026 in BAR/SCHÖ | |
| Vorlesung | Der Satz von Rice und das Postsche Korrespondenzproblem | DS4, 22. Januar 2026 in HSZ/0003 | |
| Vorlesung | Unentscheidbare Probleme formaler Sprachen | DS3, 26. Januar 2026 in BAR/SCHÖ | |
| Vorlesung | Zusammenfassung und Ausblick | DS4, 29. Januar 2026 in HSZ/0003 | |
| Konsultation | Repetitorium (2) | DS3, 2. Februar 2026 in BAR/SCHÖ | |
| Konsultation | Besprechung der Probeklausur | DS4, 5. Februar 2026 in HSZ/0003 |
Kalender
