| 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, link tbd. | 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 | 28.04.2026 |
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
Übungsblätter werden hier zur Verfügung gestellt.
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 |
Korrespondenz zwischen Vorlesungsteilen und Skript
| Vorlesungsteil | Abschnitte im Skript |
|---|---|
| 1a | 1, 2.1 (zu Hause: 2.2–2.5) |
| 1b | 3.1, 3.2 bis Anfang 3.2.2 |
| 1c | 3.2.2, 3.3–3.6 |
| 2a | 3.2.1, 3.5 |
| 2b | 4.1 |
| 2c | 4.11 |
| 3a | 4.2, 4.3 |
| 3b | 4.4, 4.5 |
| 3c | 4.6 |
| 4a | 4.7, 4.8 |
| 4b | 4.12, 4.13 |
| 4c | 4.9 |
| 5a | 4.10, 4.11 |
| 5b | 5.1, 5.2 |
| 5c | 5.4 |
| 6a | 5.3, 5.5, 5.9 |
| 6b | 5.2 bis Anfang 5.2.1, 5.6 |
| 6c | 5.7 bis Anfang 5.7.2, 5.7.2.2 |
| 7a | 5.7.2.1, 5.7.2.3, 5.7.2.4 |
| 7b | 5.8 |
| 7c | 6.2, 6.3 bis Anfang 6.3.1, 7 |
| 8a | 6.1, 6.3.1, 6.4, 6.5 |
| 8b | 3.3 |
| 8c | 8, 9.1, 9.2 |
| 9a | 9.3, 10.1 |
| 9b | 10.2, 10.3–10.5 |
| 9c | 12 |
| 10a | 11 |
| 10b | 13.1, 13.2 bis Anfang 13.2.2 |
| 10c | 13.2.2–13.2.4, 13.3 |
| 11a | 13.4, 13.5 |
| 11b | 14 |
| 11c | 15 bis Anfang 15.2 |
| 12a | 15.2 |
| 12b | 16 bis Anfang 16.2 |
| 12c | 16.2–16.4 |
| 13a | 16.5–16.9 |
| 13b | 16.10–16.13 |
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.
Falls Sie einen Nachteilsausgleich in Anspruch nehmen möchten, melden Sie sich bitte mindestens eine Woche im Voraus bei Jan Johannsen.
Reguläre Klausur
Informationen zur regulären Klausur werden hier bekanntgegeben.
Wiederholungsklausur
Informationen zur Wiederholungsklausur werden hier bekanntgegeben.