| Inhalt | Organisation | Zeit und Ort | Chat | Material | Planung | Abgabe von Übungsblättern | Klausuren |
Formale Sprachen und Komplexität (FSK, SoSe 2026)
Vorlesung, 3(+1)-std., Johannsen; Übungen 2-std., Lempa, Maio
Inhalt
Die Vorlesung behandelt Grundlagen der theoretischen Informatik: Sie gibt Einführungen in die Theorie der formalen Sprachen und Automaten sowie in die Berechenbarkeits- und Komplexitätstheorie. Die Veranstaltung orientiert sich inhaltlich und strukturell am Lehrbuch von Schöning (Theoretische Informatik – kurz gefasst). Themen sind:
Automaten und Formale Sprachen:
Deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, KellerautomatenBerechenbarkeit:
Turing-Maschinen, Churchsche These, Unentscheidbarkeit, Halteproblem, ReduktionenKomplexität:
Die Klassen P und NP, NP-vollständige Probleme, Polynomialzeit-Reduktionen
Neben der Vorlesung (3V) und den Übungen (2Ü) wird eine optionale Zentralübung (ca. alle 2 Wochen, 2-stündig) angeboten. Diese dient zum Wiederholen und zum Einüben des Stoffs, aber es wird kein neuer Stoff behandelt.
Organisation
Umfang: 3(+1)+2 Semesterwochenstunden
Vorlesung + Zentralübung: PD Dr. Jan Johannsen
Übung: Elisabeth Lempa, Luca Maio
Bitte melden Sie sich über das LSF zur Veranstaltung an, damit die Belegung und Leistungsverbuchung reibungslos ablaufen kann.
Die Abgabe der Übungsblätter erfolgt über Moodle. Der Einschreibeschlüssel für den Moodle-Kurs lautet FSK26.
Zeit und Ort
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| Vorlesung | Di 14‑17 | GSP A 240 | 14.04.2026 |
| Zentralübung | Mi 12‑14, ca. 2‑wöchig | GSP A 240 | 15.04.2026 |
| Übungsgruppe A | Do 12‑14 | GSP M 109 | 16.04.2026 |
| Übungsgruppe B | Fr 12‑14 | GSP M 109 | 17.04.2026 |
| Übungsgruppe C | Fr 14‑16 | GSP M 109 | 17.04.2026 |
| Übungsgruppe D | Fr 16‑18 | Online* | 17.04.2026 |
| Übungsgruppe E | Mo 10‑12 | GSP M 109 | 20.04.2026 |
| Übungsgruppe F | Mo 12‑14 | GSP M 109 | 20.04.2026 |
| Übungsgruppe G | Mo 16‑18 | GSP M 109 | 20.04.2026 |
(*) Bei Problemen mit dem Audio, verwenden Sie bitte einen Chrome-based Browser.
Hinweis: An allen gesetzlichen Feiertagen sowie in der Pfingstwoche (25.05. – 29.05.) finden keine Tutorien statt.
Chat
Für die Vorlesung gibt es einen Zulip-Chatraum, in dem Sie sowohl organisatorische als auch inhaltliche Fragen stellen können. Bitte verwenden Sie wenn möglich diesen Chatraum, anstatt uns Emails zu schreiben, damit Ihre Mitstudierenden auch von den Antworten profitieren können.
Material
Die Klausuren von 2025:
Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)Die Klausuren von 2024:
Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)Die Klausuren von 2019:
Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)Die LMUcast-Playlist aus den SoSe 2021/2022 ist hier verfügbar. Die Nutzung dieser Videos erfolgt auf eigene Verantwortung der Studierenden. Der Inhalt der Vorlesung im SoSe 2026 kann von den Inhalten in den vorherigen Jahren abweichen. Insbesondere werden die Themen DFA-Minimierung und linear beschränkte Turingmaschinen anders behandelt. Allein der Inhalt der Vorlesung im SoSe 2026 ist für die Prüfung im SoSe 2026 verbindlich.
Übungsblätter
| Übungsblatt | Präsenzaufgaben (Besprechung / Lösung) | Klausurvorbereitungs-Aufgaben (Abgabe / Lösung) |
|---|---|---|
| Blatt 0 | Besprechung 16.04.‑20.04. Loesung | – |
| Blatt 1 | Besprechung 23.04.‑27.04. Loesung | Abgabe bis 05.05., 14:00 |
| Blatt 2 | Besprechung 30.04.‑04.05. | Abgabe bis 12.05, 14:00 |
| Blatt 3 | Besprechung 07.05.‑11.05. | Abgabe bis 19.05., 14:00 |
| Blatt 4 | Besprechung 14.05.‑18.05. | Abgabe bis 02.06., 14:00 |
| Blatt 5 | Besprechung 21.05.‑01.06. | Abgabe bis 09.06., 14:00 |
| Blatt 6 | Besprechung 04.06.‑08.06. | Abgabe bis 16.06., 14:00 |
| Blatt 7 | Besprechung 11.06.‑15.06. | Abgabe bis 23.06., 14:00 |
| Blatt 8 | Besprechung 18.06.‑22.07. | Abgabe bis 30.06., 14:00 |
| Blatt 9 | Besprechung 25.06.‑29.06. | Abgabe bis 07.07., 14:00 |
| Blatt 10 | Besprechung 02.07.‑06.07. | Abgabe bis 14.07., 14:00 |
| Blatt 11 | Besprechung 09.07.‑13.07. | Abgabe bis 21.07., 14:00 |
| Blatt 12 | Besprechung 16.07.‑20.07. | Abgabe bis 28.07., 14:00 |
Literatur
Uwe Schöning: Theoretische Informatik – kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008
Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002
John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3. Auflage, 2006
Ingo Wegener: Theoretische Informatik – eine algorithmenorientierte Einführung, 3. Auflage, Teubner Verlag, 2005
Nützliche Webseiten
Automata Tutor: ein Online-Werkzeug zum Lernen von Automatentheorie
Online Turing Machine Simulator: Online-Werzkeug zum Simulieren von Turingmaschinen
Planung
| Termin | Inhalte |
|---|---|
| 14.04. | Vorlesung 1a: Begrüßung, Organisatorisches, Inhaltsübersicht und Grundlagen |
| Vorlesung 1b: Grammatiken und die Chomsky‑Hierarchie | |
| Vorlesung 1c: Weitere Grammatikbegriffe sowie Eigenschaften von Sprachen | |
| 15.04. | Zentralübung 1: Wörter, Beweise, Grammatiken, Chomsky‑Hierarchie |
| 21.04. | Vorlesung 2a: Grammatikbeispiele, Mehrdeutigkeit und Entfernen von Epsilon‑Produktionen |
| Vorlesung 2b: Deterministische endliche Automaten | |
| Vorlesung 2c: Minimierung von deterministischen endlichen Automaten | |
| 28.04. | Vorlesung 3a: Regularität von deterministischen endlichen Automaten und nichtdeterministische endliche Automaten |
| Vorlesung 3b: Determinisierung von endlichen Automaten | |
| Vorlesung 3c: Nichtdeterministische endliche Automaten mit Epsilon‑Übergängen | |
| 29.04. | Zentralübung 2: DFAs, NFAs, Äquivalenz |
| 05.05. | Vorlesung 4a: Reguläre Ausdrücke |
| Vorlesung 4b: Das Pumping‑Lemma für reguläre Sprachen | |
| Vorlesung 4c: Eigenschaften von regulären Sprachen | |
| 12.05. | Vorlesung 5a: Der Satz von Myhill und Nerode |
| Vorlesung 5b: Die Chomsky‑Normalform | |
| Vorlesung 5c: Das Pumping‑Lemma für kontextfreie Sprachen | |
| 19.05. | Vorlesung 6a: Die Greibach‑Normalform und Eigenschaften von kontextfreien Sprachen |
| Vorlesung 6b: Der CYK‑Algorithmus | |
| Vorlesung 6c: Kellerautomaten | |
| 20.05. | Zentralübung 3: Reguläre Ausdrücke, Abschluss, Pumping‑Lemmas |
| "Pfingstdienstag" (vorlesungsfrei) | |
| 02.06. | Vorlesung 7a: Äquivalenz von kontextfreien Sprachen und von Kellerautomaten |
| Vorlesung 7b: Turingmaschinen | |
| Vorlesung 7c: Linear beschränkte Turingmaschinen (Fortsetzung) | |
| 03.06. | Zentralübung 4: Minimierung, PDAs, Turingmaschinen |
| 09.06. | Vorlesung 8a: Entscheiden des Wortproblems für Typ 1‑Grammatiken |
| Vorlesung 8b: Intuitive und Turing‑Berechenbarkeit | |
| Vorlesung 8c: Konstruktion von Turingmaschinen und LOOP-Programme | |
| 16.06. | Vorlesung 9a: WHILE- und GOTO-Programme |
| Vorlesung 9b: Die Ackermannfunction | |
| Vorlesung 9c: Primitiv und my‑rekursive Funktionen | |
| 17.06. | Zentralübung 5: Berechenbarkeit, CYK, Myhill‑Nerode |
| 23.06. | Vorlesung 10a: Unentscheidbarkeit und das spezielle Halteproblem |
| Vorlesung 10b: Reduktion und der Satz von Rice | |
| Vorlesung 10c: Das Postsche Korrespondenzproblem | |
| 30.06. | Vorlesung 11a: Laufzeitkomplexität und die Klassen P und NP |
| Vorlesung 11b: NP‑Vollständigkeit | |
| Vorlesung 11c: Eigenschaften der Klassen P und NP | |
| 01.07. | Zentralübung 6: Reduktionen, Rice, PCP, Rekursion |
| 07.07. | Vorlesung 12a: NP‑Vollständigkeit von SAT |
| Vorlesung 12b: NP‑Vollständigkeit von 3‑CNF‑SAT | |
| Vorlesung 12c: NP‑Vollständigkeit von CLIQUE, INDEPENDENT‑SET und VERTEX‑COVER | |
| 14.07. | Vorlesung 13a: NP‑Vollständigkeit von SET‑COVER, SUBSET‑SUM, KNAPSACK, PARTITION und BIN‑PACKING |
| Vorlesung 13b: NP‑Vollständigkeit von GRAPH‑COLORING, (UN)DIRECTED‑HAMILTON‑CYCLE und TRAVELING‑SALESPERSON | |
| Vorlesung 13c: Wiederholung und Fragestunde | |
| 15.07. | Zentralübung 7: CLIQUE, GRAPH‑COLORING, KNAPSACK |
Abgabe von Übungsblättern
Die Übungsblätter müssen jeweils bis 14:00 Uhr am angegebenen Tag auf Moodle abgegeben werden. Verspätete Abgaben sind nicht möglich. Lösungsvorschläge der Klausurvorbereitungs-Aufgaben werden jeweils nach Ende der Abgabefrist unter Material veröffentlicht.
Klausuren
Bei den Klausuren sind Hilfsmittel nicht erlaubt. Auch das Mitführen ausgeschalteter elektronischer Geräte wird als Betrugsversuch gewertet. Die Aufgabenstellungen der Klausuren sind auf Deutsch, Sie dürfen aber
wahlweise auf Deutsch oder Englisch antworten.
Falls Sie einen Nachteilsausgleich in Anspruch nehmen möchten, melden Sie sich bitte mindestens eine Woche im Voraus bei Jan Johannsen.
Reguläre Klausur
Die reguläre Klausur wird am 05.08.2026 ab 14:00 Uhr stattfinden. Zur Teilnahme ist eine Anmeldung über das LSF notwendig.
Wiederholungsklausur
Teilnahme an der Wiederholungsklausur ist auch ohne Teilnahme an der regulären Klausur möglich. Das Datum der Wiederholungsklausur ist noch nicht bekannt.