04-00-0091-vu Formale Grundlagen der Informatik I: Automata and Formal Languages

Lehrende: Prof. Dr. rer. nat. Martin Otto; M.Sc. Julian Bitterlich; M.Sc. Felix Canavoi; Dr. rer. nat. Kord Eickmeyer; M.Sc. Daniel Günzel

Veranstaltungsart: Vorlesung und Übung

Orga-Einheit: FB04 Mathematik

Anzeige im Stundenplan: FGdI I

Fach:

Anrechenbar für:

Semesterwochenstunden: 3

Unterrichtssprache: Deutsch

Min. | Max. Teilnehmerzahl: - | 40

Lehrinhalte:
Einführung: Transitionssysteme, Wörter, Sprachen; Mathematische Grundbegriffe und elementare Beweismethoden; Endliche Automaten und reguläre Sprachen; Determinismus und Nichtdeterminismus, Abschlusseigenschaften und Automatenkonstruktionen;
Sätze von Kleene, Myhill-Nerode, Pumping Lemma;
Grammatiken und Chomsky-Hierarchie,
kontextfreie Sprachen, Abschlusseigenschaften, Pumping Lemma, CYK Algorithmus;
Berechnungsmodelle: Kellerautomaten, Turingmaschinen; Entscheidbarkeit und Aufzählbarkeit in der Chomsky-Hierarchie

Literatur:
Schöning: Theoretische Informatik -- kurz gefasst

Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie

Wegener: Theoretische Informatik -- eine algorithmenorientierte Einführung

Skripte (elektronisch unter www.mathematik.tu-darmstadt.de/~otto)

Voraussetzungen:
allg. mathematisches Grundwissen

Weitere Informationen:
Der Fachbereich Mathematik empfiehlt allen Studierenden an den Übungen teilzunehmen. Auch und vor allem Studierenden, die schon mehrere Prüfungsversuche hatten. Sollten Sie aber die Modulprüfung in diesem Semester wiederholen und sich dennoch entscheiden, nicht an den Übungen teilzunehmen, so wählen Sie bitte bei Ihrer Anmeldung die Übungsgruppe "Gruppe ohne Termin".

Online-Angebote:
moodle