Formale Systeme
Formale Systeme
Course with SWS 4/2/0 (lecture/exercise/practical) in WS 2025
Lecturer
Tutor
- Stefan Borgwardt
- Maximilian Marx
- Stephan Mennicke
- Anton Claußnitzer
- Lukas Gerlach
- Florens Förster
- Cornelius Lübke
- Anna Hornschild
SWS
- 4/2/0
Modules
Examination method
- Written exam
Lecture series
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.Subscribe to events of this course (icalendar)
| Lecture | Einleitung formale Sprachen | DS3, October 13, 2025 in BAR/SCHÖ | File 1, File 2 |
| Lecture | Grammatiken und die Chomsky-Hierarchie | DS4, October 16, 2025 in HSZ/0003 | File 1, File 2 |
| Exercise | Übungsblatt 1 | File | |
| Lecture | Endliche Automaten | DS3, October 20, 2025 in BAR/SCHÖ | File 1, File 2 |
| Lecture | Nichtdeterministische Automaten | DS4, October 23, 2025 in HSZ/0003 | File 1, File 2 |
| Exercise | Übungsblatt 2 | File | |
| Lecture | Abschlusseigenschaften regulärer Sprachen | DS3, October 27, 2025 in BAR/SCHÖ | File 1, File 2 |
| Lecture | Reguläre Ausdrücke (1) | DS4, October 30, 2025 in HSZ/0003 | File 1, File 2 |
| Exercise | Übungsblatt 3 | File | |
| Lecture | Reguläre Ausdrücke (2) | DS3, November 3, 2025 in BAR/SCHÖ | File 1, File 2 |
| No session | Interne Veranstaltung | DS4, November 6, 2025 in HSZ/0003 | |
| Exercise | Übungsblatt 4 | File | |
| Lecture | Minimale Automaten (1) | DS3, November 10, 2025 in BAR/SCHÖ | File 1, File 2 |
| Lecture | Minimale Automaten (2) | DS4, November 13, 2025 in HSZ/0003 | File 1, File 2 |
| Exercise | Übungsblatt 5 | File | |
| Lecture | Grenzen regulärer Sprachen / Probleme für Automaten | DS3, November 17, 2025 in BAR/SCHÖ | File 1, File 2 |
| Lecture | Von regulären zu kontextfreien Sprachen | DS4, November 20, 2025 in HSZ/0003 | File 1, File 2 |
| Exercise | Übungsblatt 6 | File | |
| Lecture | Das Wortproblem für kontextfreie Sprachen | DS3, November 24, 2025 in BAR/SCHÖ | File 1, File 2 |
| Lecture | Das Pumping Lemma kontextfreier Sprachen | DS4, November 27, 2025 in HSZ/0003 | File 1, File 2 |
| Exercise | Übungsblatt 7 | File | |
| Lecture | Abschlusseigenschaften kontextfreier Sprachen | DS3, December 1, 2025 in BAR/SCHÖ | File 1, File 2 |
| Lecture | Einleitung Kellerautomaten | DS4, December 4, 2025 in HSZ/0003 | File 1, File 2 |
| Exercise | Übungsblatt 8 | File | |
| Lecture | Kellerautomaten und CFGs | DS3, December 8, 2025 in BAR/SCHÖ | |
| Lecture | Deterministische Sprachen / Entscheidungsprobleme | DS4, December 11, 2025 in HSZ/0003 | |
| Lecture | Turingmaschinen | DS3, December 15, 2025 in BAR/SCHÖ | |
| Consultation | Repetitorium (1) | DS4, December 18, 2025 in HSZ/0003 | |
| Lecture | Nichtdeterministische Turingmaschinen und Unentscheidbarkeit | DS3, January 5, 2026 in BAR/SCHÖ | |
| Lecture | Typ 0 und Typ 1 | DS4, January 8, 2026 in HSZ/0003 | |
| Lecture | Berechenbarkeit und Unentscheidbarkeit | DS3, January 12, 2026 in BAR/SCHÖ | |
| Lecture | WHILE und LOOP | DS4, January 15, 2026 in HSZ/0003 | |
| Lecture | Das Halteproblem und Reduktionen | DS3, January 19, 2026 in BAR/SCHÖ | |
| Lecture | Der Satz von Rice und das Postsche Korrespondenzproblem | DS4, January 22, 2026 in HSZ/0003 | |
| Lecture | Unentscheidbare Probleme formaler Sprachen | DS3, January 26, 2026 in BAR/SCHÖ | |
| Lecture | Zusammenfassung und Ausblick | DS4, January 29, 2026 in HSZ/0003 | |
| Consultation | Repetitorium (2) | DS3, February 2, 2026 in BAR/SCHÖ | |
| Consultation | Besprechung der Probeklausur | DS4, February 5, 2026 in HSZ/0003 |
Calendar
