Theoretische Informatik: Automaten und formale Sprachen
Sommersemester 2024
bei Prof. Dr. Sibylle Schwarz
Pflichtmodul C993
im 4. Semester Bachelor Informatik,
Wahlpflichmodul für Bachelor Medieninformatik
Lernziele / Kompetenzen
Die Studierenden sind in der Lage, wichtige Klassen formaler Sprachen als Grundlage von
Programmier- und Beschreibungssprachen einzuordnen und kennen die wesentlichen Eigenschaften
der Sprachklassen.
Sie kennen die entsprechenden abstrakten Maschinenmodelle und Algorithmen und können sie zur
Darstellung und Lösung praktischer Aufgabenstellungen einsetzen. Die Studierenden wissen, dass nicht jedes formal darstellbare Problem algorithmisch lösbar ist.
Inhalt
- Formale Sprachen und verschiedene Darstellungsformen dafür
- reguläre Ausdrücke
- Wortersetzungssysteme und Grammatiken
- Chomsky-Hierarchie
- Abschlusseigenschaften verschiedener Sprachklassen
- Pumping Lemmata für reguläre und kontextfreie Sprachen
- abstrakte Maschinenmodelle:
- endliche Automaten (NFA, DFA, ...)
- Kellerautomaten (PDA)
- linear beschränkte Automaten
- Turingmaschinen
- Ausblick auf Grenzen der Berechenbarkeit
Vorlesung
Übungen
In den Übungen werden vorwiegend die Lösungen der schriftlichen
Hausaufgaben besprochen und damit die Zulassungen zur Prüfung
erworben.
Übungsaufgaben
Schriftliche Aufgaben:
Praktische Übungsaufgaben sind wöchentlich
im Autotool zu
bearbeiten.
Literaturempfehlungen
Zusammenfassung,
alle Folien
Die Unterlagen zum Modul
Theoretische Informatik: Automaten und formale Sprachen
im SS22 stehen
hier.
Bücher:
- Uwe Schöning:
Theoretische Informatik - kurzgefasst, Spektrum 2001
- John E. Hopcroft, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und
Komplexitätstheorie, Addison-Wesley 1990
- Dirk W. Hoffmann:
Theoretische Informatik, Hanser 2018
- Ulrich Hedtstück: Einführung in die Theoretische Informatik
Formale Sprachen und Automatentheorie, Oldenbourg 2012
- Lukas König, Friederike Pfeiffer-Bohnen, Hartmut Schmeck:
Theoretische Informatik – ganz praktisch, De Gruyter 2016
- Heinz-Peter Gumm, Manfred Sommer
Informatik – Band 3: Formale Sprachen, Compilerbau,
Berechenbarkeit und Komplexität, De Gruyter 2019
- Gottfried Vossen, Kurt-Ulrich Witt:
Grundkurs Theoretische Informatik, Vieweg 2006
- Renate Winter: Theoretische Informatik, Oldenbourg 2002
- Rolf Socher:
Theoretische Grundlagen der Informatik, Hanser 2008
- Alexander Asteroth, Christel Baier:
Theoretische Informatik. Eine Einführung in Berechenbarkeit,
Komplexität und formale Sprachen, Pearson 2002
Unter
http://wilfridhodges.co.uk/cognitive01.pdf
gibt es sieben uneingeschränkt richtige Hinweise zum Lernen von Mathematik, die
selbstverständlich genauso für die theoretische Informatik gelten.
https://www.imn.htwk-leipzig.de/~schwarz
mailto:sibylle.schwarz@htwk-leipzig.de