Vorlesung Formale Sprachen und Automaten (Sommer 2025)

 

Organisatorisches

• Veranstalter: Prof. Dr. Markus Lohrey
• Vorlesungstermine:
  • Dienstag, 14:15-15:45, H-C 3305
  • Donnerstag (jede gerade Woche), 14:15-15:45, AR-F 002
• Der erste Vorlesungstermin ist am 8. April.
• Die Donnerstagsvorlesung findet erstmalig am 17. April statt, danach im zweiwöchigen Rhythmus.
• Übungen:
  • Mittwoch, 10:15-11:45, H-C 7326
  • Mittwoch, 12:15-13:45, H-C 7326
  • Donnerstag, 08:15-09:45, H-C 7326
  • Freitag, 12:15-13:45, H-C 7326 (optional in Englisch)
  • Tutoren und Ansprechpersonen: Michael Figelius und Alexander Thumm
• Alle Übungsgruppen beginnen in der Woche von 14. April bis 19. April.
• Es gibt optional einen Discord-Server. Für den Link sprechen Sie bitte Ihren Übungsleiter an!

 

Einige Themen

• Formale Sprachen
• Chomsky Hierarchie
• Endliche Automaten
• Kontextfreie Grammatiken
• Kellerautomaten
• Turingmaschinen

 

Folien (deutsch)

Slides (englisch)

 

Übungsblätter

• Blatt 01 (Lösungen)
• Blatt 02 (Lösungen)
• Blatt 03 (Lösungen)
• Blatt 04 (Lösungen)
• Blatt 05 (Lösungen)
• Blatt 06 (Lösungen)
• Blatt 07 (Lösungen)
• Blatt 08 (Lösungen)
• Blatt 09 (Lösungen)
• Blatt 10 (Lösungen)
• Blatt 11 (Lösungen)
• Blatt 12 (Lösungen)
• Blatt 13 (Lösungen)
• Blatt 14 (Lösungen)

 

Klausuren

Formale Sprachen und Automaten

• Klausur vom SoSe22 (Lösung)
• Klausur vom WiSe22/23 (Lösung)
• Klausur vom SoSe24 (Lösung)

Grundlagen der theoretischen Informatik

• Klausur vom SoSe19 (Lösung)
• Klausur vom WiSe19/20 (Lösung)

 

Lehrbücher

• Uwe Schöning, Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag
• Lutz Priese, Katrin Erk, Theoretische Informatik: Eine umfassende Einführung, Springer
• Alexander Asteroth, Christel Baier, Theoretische Informatik, Pearson Studium