Theoretische Informatik

Themengebiete

schnelle Suche mit DEAs


Potenzmengenkonstruktion


  1. Übung SS2015 6.3b
  2. Tutorium SS2015 Tag 2 Aufgabe 4

Konstruktionen für DEAs/NEAs: Komplement, Vereinigung, Schnitt, Konkatenation, Iteration


Umwandlung zwischen endlichen Automaten und regulären Ausdrücken


Anwendung des Pumping‐Lemmas für REG


Äquivalenztest für DEAs


Minimierung von DEAs


Umrechnung zwischen regulären Sprachen und Sprachen vom Typ 3


  • Tutorium SS2015 Tag 3 Aufgabe 4
  • Tutorium SS2015 Tag 3 Aufgabe 5

Umwandlung einer kontextfreien Grammatik in Chomsky‐Normalform


Anwendung des Pumping‐Lemmas fuuml;r kontextfreie Sprachen


Umwandlung einer nichtverkürzenden Grammatik in eine kontextsensitive Grammatik


  • Klausur SS 2015 2b

Nachweis, dass eine gegebene Menge in P bzw. NP liegt


Nachweis der Polynomialzeit‐Reduzierbarkeit zwischen gegebenen Mengen


Aufzählbarkeit und Entscheidbarkeit von Mengen