11.4.: Einfuehrung, Inhaltsuebersicht, Chomsky Grammatiken 15.4.: Sprache einer Grammatik, Ableitungen, Chomsky-Hierarchie (Typ-0, Typ-1, Typ-2, Typ-3), Entscheidbarkeit des Wortproblems fuer Typ-1 Sprachen, BNF, Syntaxbaeume, Mehrdeutige Grammatiken. 18.4.: Typ-0..Typ-3 Sprachen, inhaerent mehrdeutige Spracehn (jeweils Def.). Endliche deterministische Automaten (DEA), nichtdeterministische endl. Automaten (NEA) , jeweils Definition und erkannte Sprache. Regularitaet (Typ-3) der von DEA erkennbaren Sprachen, Aequivalenz von DEA und NEA durch Potenzmengenkonstruktion. Letzteres wurde aus Zeitgruenden sehr gehetzt praesentiert; eine detailliertere Darstellung erfolgt am Freitag. 22.4.: Potenzmengenkonstruktion NEA->DEA detailliert praesentiert. Typ-3 Grammatik -> NEA. Regulaere Ausdruecke. 25.4.: Diagrammatischer Beweis zur Potenzmengenkonstruktion, Aequivalenz von regulaeren Ausdruecken und Automaten. Rechenregeln fuer regulaere Ausdruecke (und Sprachen): A(B+C)=AB+AC; falls epsilon nicht in A, dann X=AX+B <=> X=A*B. 29.4.: Ableitung eines regulaeren Ausdrucks von einem DEA mithilfe der Rechenre- geln. Durchgefuehrt am Beispiel eines Automaten fuer {w | |w|_1 gerade}. Pumpinglemma. Verwendung des Pumpinglemmas um zu beweisen, dass eine Sprache nicht regulaer ist. Beispiel einer Sprache, die zwar nicht regulaer ist, letzteres aber nicht mit dem Pumpinglemma gezeigt werden kann: L = {c^m a^n b^n | m,n>=0} + a*b*. Wiederholung des Begriffs Aequivalenzrelation. 2.5.: Wdh Aquivalenzklassen, Quotienten (= Menge von Aequivalenzklassen), Definition von Funktionen auf Quotienten durch Definition auf Repraesentanten. Die Myhill-Nerode Aequivalenz einer Sprache (x R_L y <=> fuer alle u.xu:L <=> yu:L). Satz von Myhill-Nerode. Existenz und Eindeutigkeit des Minimalautomaten, effektive Konstruktion desselben mit dem Algorithmus von Hopcroft. 6.5.: Beispieldurchfuehrung des Algorithmus zur Bestimmung des Minimalautomaten. Abschlusseigenschaften regulaerer Sprachen, insbes Komplement, Schnitt. Entscheidbarkeitsfragen fuer regulaere Sprache: Wortproblem, Leerheitsproblem, Aequivalenzproblem,... . Alle entscheidbar. 9.5.: Kontextfreie Sprachen Wdh. Elimination von epsilon-Produktionen. Chomsky Normalform, Konstruktion. Motivation zum Pumpinglemma fuer kontextfreie Sprachen. 13.5.: Pumping Lemma fuer kontextfreie Sprachen: Aussage, Beweis, Anwendung auf {a^nb^nc^n | n>=1} (nicht kontextfrei!). CYK Algorithmus als rekursives Programm motiviert. Naechstes Mal: effiziente Implementierung mit dynamischer Programmierung. 20.5.: CYK Algorithmus mit dynamischer Programmierung. Informelle Darstellung der Erkennung von Typ-2 Sprachen mit Kellerautomaten. 23.5.: Formale Definition von Kellerautomaten (PDA). Aequivalenz von PDA und Typ-2 Grammatiken. Abschluss von Typ-2 Sprachen unter Vereinigung 27.5.: Abschluss von Typ-2 Sprachen unter Vereinigung, Konkatenation, Stern. Beweis, dass Typ-2 Sprachen nicht unter Durchschnitt und somit auch nicht unter Komplement abgeschlossen sind. Turingmaschinen, linear beschraenkte Turingmaschinen (LBA) als Spezialfall. Typ-1 Sprachen sind durch LBA erkennbar. 30.5.: Jede durch LBA erkennbare Sprache ist Typ-1. Konstruktion der entsprechenden Grammatik ausgehend von einem LBA. Die Typ-1 Sprachen sind unter Komplement abgeschlossen (Immerman-Szelepcsenyi) Ohne Beweis!. Die Typ-0 Sprachen sind genau die von Turingmaschinen akzeptierten. 3.6.: Intuitive Berechenbarkeit. Beispiele berechenbarer und nicht berechenbarer Funktionen. Turing-Berechenbarkeit. Mehrbandturingmaschinen und deren Aequivalenz zu Einbandturingmaschinen. 6.6.: LOOP Programme, Beispiele und definierte Konzepte wie IF-THEN-ELSE. LOOP Berechenbarkeit, Wertzuweisung mit LOOP Berechenbaren Funktionen. WHILE Programme. 10.6.: GOTO-Programme; Uebersetzungen WHILE <-> GOTO, Turingmaschine->GOTO, WHILE->Turingmaschine. Kleene Normalform. Definition der primitiv rekursiven Funktionen. Beispiele kommen naechstes Mal. 13.6.: Beispiele zur primitiven Rekursion: add, mult, minus, etc. Satz: Die Cantorsche Paarungsfunktion c(x,y) = sum(i=0..x+y, i) + x ist primitiv rekursive Bijektion; ihre Inversen sind auch primitiv rekursiv. Satz: die Klasse der p.r. Funktionen stimmt mit der Klasse der LOOP berechenbaren Funktionen ueberein. 17.6.: Die mu-Rekursion. WHILE berechenbare Funktionen = mu-rekursive Funktionen. Die Ackermannfunktion. Beweis, dass sie nicht LOOP berechenbar ist. Entscheidbarkeit, semi-Entscheidbarkeit. 20.6. Das Halteproblem, Beweis der Unentscheidbarkeit des speziellen Halteproblems (Menge K). Reduktion. Ableitung der Unentscheidbarkeit des allgemeinen Halteproblems durch Reduktion. Die Kleene - Normalform in der Form : jede berechenbare Funktion f ist von der Form f(x) = U(mu t.T(e,x,t)) wobei U, T feste (unabhaengig von f) primitiv rekurtsive Funktionen sind und e von f abhaengt. Der Satz von Rice (Beweis am Freitag). 24.6.: Postsches Korrespondenzproblem, unentscheidbare Grammatikprobleme, z.B. Aequivalenz kontextfreier Grammatiken. 27.6.: Zeitkomplexitaet, die Klassen P und NP. 1.7.: Polynomielle Reduktion, NP-Haerte, NP-vollstaendigkeit. Das Problem KNF-SAT (Erfuellbarkeit von konjunktiven Normalformen) Reduktion von 3-Faerbbarkeit auf KNF-SAT. 4.7.: Satz von Cook: KNF-SAT ist NP-vollstaendig. NP-vollstaendigkeit der Probleme 3KNF-SAT, SAT (Erfuellbarkeit aussagenlogischer Formeln), SET-COVER, CLIQUE. 8.7.: Beweis der NP - Vollstaendigkeit weiterer zahlentheoretischer und kombinatorischer Probleme: VERTEX-COVER, RUCKSACK, BIN-PACKING, PARTITION. Der Beweis der NP-Haerte von 3FAERBBARKEIT wurde begonnen. 11.7. NP-Vollstaendigkeit von 3FAERBBARKEIT durch Reduktion von 3KNF-SAT. Definition der Baumweite ueber das Robber-k-Cops Spiel. 3FAERBBARKEIT fuer Graphen fester Baumweite ist in P. Die Thematik Baumweite ist nicht pruefungsrelevant. NP Vollstaendigkeit von HAMILTON (Existenz Hamiltonscher Kreise) fuer gerichtete und ungerichtete Graphen. 15.7. Goedelscher Unvollstaendigkeitssatz.