04-00-0091-vu Automaten, formale Sprachen und Entscheidbarkeit

Lehrende: Prof. Dr. rer. nat. Pascal Schweitzer; M.Sc. Simon Vincent Raßmann

Veranstaltungsart: Vorlesung und Übung

Orga-Einheit: FB04 Mathematik

Anzeige im Stundenplan: FGdI I

Fach:

Anrechenbar für:

Semesterwochenstunden: 3

Unterrichtssprache: Deutsch

Min. | Max. Teilnehmerzahl: - | -

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

Weitere Informationen:
durchgeführt als Teil einer (4+2) Veranstaltung

Online-Angebote:
https://moodle.informatik.tu-darmstadt.de/course/view.php?id=1516