Formale Systeme
Winter 2021/22
Meine Übung findet am
Freitag von 920 Uhr bis 1050 Uhr (2. Doppelstunde)
statt und startet ab 05. November 2021.

Inhalte der Übungen

Die Vorlesung "Formale Systeme" beschäftigt sich mit den Grundlagen der formalen Sprachtheorie, wie sie in der Vorlesung "Algorithmen und Datenstrukturen" bereits angeklungen ist, der Automatentheorie sowie der Aussagenlogik. In den Übungen wollen wir die Erkenntnisse aus der Vorlesung verstehen, anwenden und festigen.

News

  • 05.10.2021: Herzlich Willkommen im Kurs "Formale Systeme" im Wintersemester 2021/22. Die Übungen starten ab dem 18.10.2021 in Präsenz oder online (je nach Übungsgruppe). Meine Übung wird in Präsenz stattfinden. Jedoch kann es sein, dass gesetzliche Bestimmungen dazu führen, dass ich erst ab November vor euch stehen darf. Ob dies wirklich der Fall sein wird und wie die Zwischenzeit überbrückt wird, kann erst im Laufe der ersten Vorlesungswoche geklärt werden.

Informationen

Alle für die Lehrveranstaltungen relevanten Informationen findet ihr auf der Website bzw. im OPAL-Kurs. Die Vorlesung wird online stattfinden und von Hannes Straß gehalten. Bei Fragen oder Problemen könnt ihr euch im OPAL-Forum oder dem Matrix-Chat austauschen - oder euch an mich oder an Dörthe Arndt wenden. Mich erreicht ihr auch schnell und problemlos via Telegram @oakoneric.

Übungsmaterial

Die Materialien zur Vorlesung und Übung seitens des Lehrstuhls findet ihr auf der Website der Lehrveranstaltung.

Die in meinen Übungen verwendeten Materialien habe ich größtenteils in meiner Freizeit erstellt. Sie stammen insbesondere nicht vom Lehrstuhl und können damit trotz gründlicher Arbeit noch Fehler enthalten. Die Folien sollen keineswegs den aktiven Besuch der Übungen ersetzen, sondern vielmehr eine Hilfestellung sein um sich während der Übung auf das Verständnis konzentrieren zu können und das Nacharbeiten zu erleichtern. Die Slides und den zugehörigen Latex-Code dazu findet ihr in meinem entsprechenden Github-Repository. Findet ihr einen Fehler in meinen Lösungen, dann fühlt euch eingeladen mir dies mitzuteilen oder direkt selbst mit einem Request zu beheben.

Übungsübersicht

Teil 1: Formale Sprachen & Automatentheorie

Blatt Inhalte Download
3 Reguläre Sprachen Slides Handout
4 Reguläre Ausdrücke Slides Handout
5 Reguläre Ausdrücke Slides Handout
6 Pumping-Lemma und kontextfreie Grammatiken Slides Handout
7 Kontextfreie Sprachen Slides Handout
8 Kellerautomaten Slides Handout
9 Kellerautomaten Slides Handout
10 Turingmaschinen Slides Handout

Teil 2: Aussagenlogik

Blatt Inhalte Download
11 Aussagenlogik - Syntax und Semantik Slides Handout
12 Äquivalenzen und Resolution
  • Meine Notizen der Übung (keine Musterlösung, ohne Garantie)
Slides Handout
13 Resolution und Komplexität
  • Meine Notizen der Übung (keine Musterlösung, ohne Garantie)
  • In meinen Slides auf Folie 7 hatte sich ein kleiner Fehler eingeschlichen - die Constraints für die Reduktion des k-Färbbarkeitsproblem auf SAT hatten an zwei Stellen den falschen Junktor. Ich habe die Korrektur in den Slides hervorgehoben.
Slides Handout
14 Das letzte Übungsblatt
  • Meine Notizen der Übung (keine Musterlösung, ohne Garantie)
Slides Handout