Theoretische Informatik II - Sommersemester 2024

Programmierübung. Einen Anfang einer Elm-Implementierung für binäre Suchbäume finden Sie in BST.elm. Meine Empfehlung: vervollständigen Sie die Funktion insert und schreiben Sie noch delete. Dann kopieren Sie die Datei und implementieren einen Treap. insert bei Treaps sollte nicht allzu schwer sein. Eine unvollständige Java-Implementierung finden Sie in BT.java; dort finden Sie auch die main-Methode, die das Einlesen der User-Befehle erledigt, so dass Sie sich auf die Datenstruktur konzentrieren können.

Formale Sprachen. Informelle Einfühunrg mit Beispielen. Format von Emailadressen. Abstraktere Beispiele wie Sprache der Wörter, die gleich viele $a$'s wie $b$' enthalten.

Formale Sprachen. Formale Definition von kontextfreien Sprachen. Reguläre Sprachen, mehrere Beispiele, Übungen. Endliche Automaten.

Universelle Turingmaschine.

Unentscheidbare Probleme. Halteproblem. Postsches Korrespondenzproblem.

Unentscheidbare Probleme. Wortproblem für verschiedene Grammatiken (reguläre und kontextfreie: entscheidbar); Unentscheidbarkeit für allgemeine Grammatiken. Unentscheidbarkeit des Schnittproblems und Mehrdeutigkeitsproblems für kontextfreie Sprachen.