Kursinformation

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
\newline
Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie
\newline
Wegener: Theoretische Informatik -- eine algorithmenorientierte Einführung
\newline
Skript (elektronisch unter www.mathematik.tu-darmstadt.de/˜otto)

Voraussetzungen
keine

Online-Angebote
moodle