Übersicht
Veranstaltungsart: Vorlesung + Übung (Bachelor)
Credits: 4V + 2Ü, 8 LP
Turnus: Jedes Sommersemester
Empfohlenes Semester:
2. Fachsemester
2. Fachsemester
Prüfung: Klausur (120 Minuten)
Sprache: Deutsch
Inhalt
Ziel der Vorlesung ist eine Einführung in formale Sprachen und Automaten. Themenauswahl:
- Endliche Autaten und reguläre Sprachen
- DFA, NFA, reguläre Ausdrücke, Pumping-Lemma, Abschlusseigenschaften, Nerode-Automat
- Kellerautomaten und kontextfreie Sprachen
- CFG (Normalformen, Syntaxbaum, Pumping-Lemma, Ein- und Mehrdeutigkeit), PDA (Odgens Lemma), Abschlusseigenschaften, deterministisch kontextfreie Sprachen
- Turingmaschinen und Berechenbarkeit
- Churchsche These, Turingmaschinen (nichtdeterministisch, Mehrband), Random Access Machines, mu-rekursive Funktionen, (Semi-)Entscheidbarkeit, Wortproblem, Halteproblem, Leerheitsproblem, Satz von Rice, Postsches Korrespondenzproblem, Reduktion
- Chomsky-Hierarchie
- Uneingeschränkte Grammatiken, Kontextsensitive Sprachen, Linear beschränkte Turingmaschinen