C993 – Automata and Formal Languages

Module
Automata and Formal Languages
Automaten und formale Sprachen
Module number
C993 [INB3010, MIB8310]
Version: 1
Faculty
FIM-INF: Informatikstudiengänge - Fakultät Informatik und Medien
Level
Bachelor
Duration
1 Semester
Semester
Winter semester
Module supervisor

Prof. Dr. rer. nat. Sibylle Schwarz
sibylle.schwarz@htwk-leipzig.de
Lecturer(s)

Prof. Dr. rer. nat. Sibylle Schwarz
sibylle.schwarz@htwk-leipzig.de
Course language(s)

German
in "Automaten und formale Sprachen"
ECTS credits

5.00 credits

Workload

150 hours

Courses

4.00 SCH (2.00 SCH Vorlesung | 2.00 SCH Other)
Self-study time

94.00 hours

Pre-examination(s)

Prüfungsvorleistung Beleg
in "Automaten und formale Sprachen"

Prüfungsvorleistung Präsentation
in "Automaten und formale Sprachen"
Examination(s)

Prüfung Klausurarbeit
Module examination | Examination time: 90 minutes | Weighting: 100% | not to be compensated
in "Automaten und formale Sprachen"
Form of teaching

-
Media type

keine Angabe
Instruction content/structure

Formale Sprachen und verschiedene Darstellungsformen dafür, reguläre Ausdrücke Grammatiken (Chomsky-Hierarchie, Pumping Lemmata)

Berechnungsmodelle: endliche Automaten, Kellerautomaten,Turingmaschinen 

Ausblick auf Grenzen der Berechenbarkeit
Qualification objectives

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.
Special admission requirements

Keine
Recommended prerequisites

anwendungsbereite Kenntnisse auf den Gebieten Modellierung, Logik, Algorithmen und Datenstrukturen, Aufwandsabschätzungen
Literature
  • J. E. Hopcroft, J. D. Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie", Addison-Wesley, aktuelle Auflage.
  • U. Schöning: "Theoretische Informatik - kurzgefasst", Spektrum, aktuelle Auflage.
  • D. Hoffmann: "Theoretische Informatik", Hanser, 2009.
  • R. Socher: "Theoretische Grundlagen der Informatik", Hanser, 2008
  • G. Vossen, K.-U. Witt: "Grundkurs Theoretische Informatik", Springer Vieweg, aktuelle Auflage.
Current teaching resources

Lehrmaterial und aktuelle Informationen: https://informatik.htwk-leipzig.de/schwarz
Notes

regelmäßiges erfolgreiches Lösen der praktischen Übungsaufgaben (PVB) und 3 Kurzvorträge zu schriftlichen Übungsaufgaben (PVP)
Applicability

Pflichtmodul: INB, Wahlpflichtmodul: MIB
Link to course/learning resources in OPAL/Moodle/etc.
Close detail view
© Modulux (Version 4.1)