Beschreibung
Kapitel
Über den Videoplayer lassen sich über den CC Button in der Playerleiste Untertitel aktivieren, die
automatisiert durch den Speech-to-Text Dienst Open AI Whisper generiert wurden. Der Dienst bietet
üblicherweise eine hohe Genauigkeit bzw. Korrektheit, die aber variieren kann.
Beschreibung
· Grammatiken der Chomsky Hierarchie (Typ3-Typ 0)
26.10.2010
Vorlesungsaufzeichnungen 25.10.2010 01:33:42 3.766 Terminologie Einführung; 1. Terminologie: 1.1 Sprache, Grammatik: Alphabet und Wort, Sprache, Reguläre Ausdrücke, Grammatik, einfache Grammatiken, Ableitung, Rechnung, Indeterminismus, Erzeugte Sprache L(G), Äquivalenz, Lemma 1.9, Dycksprache. 29.10.2010 01:17:54 1.609 Terminologie 1.2 Warum Sprachen?: Fakt 1.11, Boolesche Ausdrücke, Fakt 1.12, Definition 1.13 (Satisfiability), Graphen, Definition 1.14 (Erreichbarkeitsproblem), Definition 1.15. 1.3 Die Chomsky-Hierarchie: Definition 1.16 (Sprachklassen), kontextfrei (cf), kontextsensitiv (cs), beschränkt, Definition 1.17 (Sprachklassen), Beispiel 1.18. 1.4 Probleme über Sprachen: Definition 1.19 (Problem, Algorithmus), Beispiel 1.20 (Einige Probleme). 1.5 Endlich, unendlich und dann?: Definition 1.21 (Endlich, unendlich), Mögliche Antworten, Lemma 1.22 01.11.2010 01:31:03 2.026 Automatentheorie und formale Sprachen Automatentheorie und formale Sprachen: 2.1 DEAen (e.a.): Darstellung als Graph, Definition 2.1 (Endlicher Automat), Beispiel 2.2, Definition 2.3 (Von einem e.a. akzeptierte Sprache), Beispiel 2.4, Beispiel 2.5, Beispiel 2.6. 2.2 NDEAs (nd e.a.): In-/ Determinierte endliche Automaten, Definition 2.7 (Indeterminierter endlicher Automat), Schreibweisen, Definition 2.8 (Von nd e.a. akzeptierte Sprache), Indeterminismus, Darstellung als Graph, Idee, Lemma 2.9 05.11.2010 01:28:58 1.256 Automatentheorie und formale Sprachen 2.2 NDEAs (nd e.a.): Lemma 2.9, Theorem 2.10, Beweis, Ein konkretes Beispiel, in-/determinierter Automat, Konstruktion determinierter endlicher Automat, Übungsblatt 2. 2.3 Automaten mit E-Kanten: Definition 2.11 (Automat mit E-Kanten), Definition 2.12 (E-nd e.a. akzeptierte Sprache), Theorem 2.13 (E-nd e.a. gleich mächtig wie nd e.a.) 08.11.2010 01:34:11 1.601 Automatentheorie und formale Sprachen 2.3 Automaten mit E-Kanten: Theorem 2.13 (E-nd e.a. gleich mächtig wie nd e.a.), Figure. 2.4 ea = Typ 3: Theorem 2.14 (Satz von Kleene: RAT = L3), Beispiel 2.15. 2.5 Pumping Lemma: (Nicht) reguläre Sprache, Theorem 2.16 (Pumping-Lemma für L3-Sprachen), Beweis 1. Fall / 2. Fall, Nicht rationale Sprachen, Theorem 2.17 (Erweitertes Pumping-Lemma für L3). 15.11.2010 01:29:34 1.078 Automatentheorie und formale Sprachen 2.5 Pumping Lemma: Theorem 2.17 (Erweitertes Pumping-Lemma für L3), Wiederholung. 2.6 Wortprobleme: Definition 2.18 (erreichbar, co-erreichbar, trim), Figure, Definition 2.19 (Teilautomaten), Definition 2.20, Lemma 2.21, Lemma 2.22, Lemma 2.23, Korollar. 2.7 Rational-Regulär: Theorem 2.24 (Hauptsatz von Kleene), Induktionsanfang, Induktionsschritt. 22.11.2010 01:33:44 1.298 Kellerautomaten 3.5 PDAs: Definition 3.23 (Push-Down-Automat), Übergangsrelation, Definition 3.24 (Konfiguraion des PDA), Definition 3.25 (Rechnung), Definition 3.26 (von PDA akzeptierte Sprache), Beispiel 3.27, Beispiel 3.28, Theorem 3.29 (finale Zustände -> leerer Keller), Theorem 3.30 (leerer Keller -> finale Zustände), Theorem 3.31 (PDA akzeptieren L2), Lemma 3.32 (cf-Grammatik -> PDA) und Beweis, M. 3.4 Pumping-Lemma für cf: Theorem 3.21 (Pumping Lemma für cf Sprachen), Theorem 3.22 (Ogdens Lemma) 26.11.2010 01:26:20 834 Kellerautomaten 3.4 Pumping-Lemma für cf: Theorem 3.21 (Pumping Lemma für cf Sprachen), Beweis. 3.5 PDAs: Theorem 3.31 (PDA akzeptieren L2), Lemma 3.32 (cf-Grammatik -> PDA), Idee, M, n -> n+1, Regel, Lemma 3.34 (PDA -> cf-Grammatik), Variablen, Übergänge, Kombinationen, Durchlaufene Zustände, Ableitung, Grammatik (-Regeln). 3.6 Abschlusseigenschaften: Theorem 3.36 (Abschlusseigenschaften von L2), Theorem 3.37. 3.1 Ableitungsbäume: Definition 3.1 (Ableitungsbaum zu einer Grammatik), Ablesen eines Wortes, Idee, Theorem 3.2, Figure, Beispiel 3.3, Definition 3.4 (Linksableitung), Definition 3.5 (Mehrdeutigkeit), Beispiel 3.6, Beispiel 3.7. 30.11.2010 01:30:24 860 Kellerautomaten 3.2 Umformungen: Definition 3.8 ((co-) erreichbare, nutzlose Symbole), Theorem 3.9 (cf-Grammatik ohne nutzlose Symbole), Algorithmus und Grammatik co-erreichbarer Variablen, Theorem 3.10 (Normalform), Definition 3.11 (E-Regel, nullbare Variablen), Theorem 3.12 (E-Regeln sind eliminierbar), Induktionsanfang und Induktionsschritt, Regel, Beispiel 3.13, Lemma 3.14, Definition 3.15 (Kettenproduktion), Theorem 3.16 (Kettenproduktionen sind eliminerbar), Theorem 3.17 (Normalform für cf. Grammatiken). 3.3 Normalformen: Definition 3.18 (Chomsky-Normalform), Theorem 3.19 (Chomsky-Normalform), Definition 3.20 (Greibach-Normalform). 3.7 Wortprobleme: Das Wortproblem und L3/L2, Chart-Parsing, Beispiel 3.38 06.12.2010 01:31:06 1.073 Turing Maschinen 4. Turing Maschinen (re): Berechenbarkeit und Komplexität, Robustheit, Ausblick und Eigenschaften von Turing-Maschinen. 4.1 DTM’n: Definition 4.1 (Turing-Maschine (DTM)), Funktion, Band einer DTM ist einseitig unbeschränkt, Beispiel 4.2 (a durch b ersetzen), Beispiel 4.2 (L), Beispiel 4.4 (Copy), Fakt 4.5 (Übergangsfunktion nicht überall definiert), Beispiel 4.6 (Print n), 4 Elemente, Definition 4.7 (Konfiguration einer DTM), Definition 4.8 (Nachfolgekonfiguration), Definition 4.9 (Eingabe), Definition 4.10 (Halten, Hängen), Definition 4.11 (Rechnung), Beispiel 4.12 (Replace(a)), Definition 4.13 (TM-berechenbar), Definition 4.14 (Von einer DTM akzeptierte Sprache), Definition 4.15 (TM part, TM), Kodieren. 4.2 Flußdiagramme: Graphische Darstellung der Übergangsfunktion einer DTM, Elemente, Beispiel 4.16, Beispiel 4.17 (R), Beispiel 4.18 (L), Beispiel 4.19 (Copy), Sie rechnet so. 10.12.2010 01:28:43 731 Turing Maschinen 4.2 Flußdiagramme: Beispiel 4.20 (SR), Beispiel 4.21 (SL). 4.3 Varianten von TMn: Turing-Maschine die nie hängen bleibt, Definition 4.22 (zw-DTM), Theorem 4.23 (Simulation von zw-DTM durch DTM), Beweis, Definition 4.24 (DTM mit k Halbbändern, k-DTM), Theorem 4.25 (Simulation von k-DTM durch DTM). 4.4 NTMn: Definition 4.26 (NTM), Definition 4.27 (Nachfolgekonfiguration, Rechnung), Definition 4.28 (NTM: Halten, Hängen, Akzeptieren), Haltekonfigurationen, Beispiel 4.29, Beispiel 4.30 (Composite), Theorem 4.31 (Simulation von NTM durch DTM). 4.5 Universelle DTMn: Übergänge, Beispiel 4.32 (Gödelisierung). 13.12.2010 01:34:13 649 Turing Maschinen Übungsblätter 4 und 5. 4.8 Unentscheidbar: Definition 4.43 (Busy Beaver), Theorem 4.44 (BB ist nicht berechenbar), Beweis. 4.7 DTM Typ 0: Satz 4.39 (Rekursiv aufzählbar = Typ 0), Lemma 4.40 (DTM akzeptierte Sprachen vom Typ 0), Beweis, Lemma 4.41 (Rekursiv aufzählbar impliziert Typ 0), Beispiel 4.42 (TM mit Begrenzern), zwei- und dreistöckige Symbole, Ableitung. 4.6 Entscheidbar/Aufzählbar: Akzeptieren und Entscheiden, Definition 4.33 (Entscheidbar), Definition 4.34 (Akzeptierbar), Definition 4.35 (Rekursiv Aufzählbar (r.e.)), Satz 4.36 (Akzeptierbar = Rekursiv Aufzählbar) 03.01.2011 01:31:48 737 Turing Maschinen Übungsblatt 6. 4.6 Entscheidbar/Aufzählbar: Satz 4.37 (Entscheidbar vs. Akzeptierbar). 4.8 Unentscheidbar: Definition 4.45 (Probleme über DTMn als Sprachen), Definition 4.46 (Jede Zahl ist Gödelnummer), Definition 4.47 (Allgemeines Hauptproblem), Definition 4.48 (Spezielles Halteproblem), Definition 4.49 (Null-Halteproblem), Definition 4.50 (Leerheitsproblem), Definition 4.51 (Totalitätsproblem), Definition 4.52 (Gleichheitsproblem), Definition 4.53 (Entscheidungsproblem), Satz 4.54 (Spezielles Halteproblem ist unentscheidbar), Beweis, Satz 4.55 (Akzeptierbarkeit von H), Satz 4.56 (H ist nicht aufzählbar), totale und berechenbare Funktion, Definition 4.57 (Reduktion), Satz 4.59 (Unentscheidbarkeit von H0), Per Reduktion Unentscheidbarkeit von Problemen zeigen 10.01.2011 01:29:02 838 Turing Maschinen und P versus NP Turing Maschinen: Definition 4.57 (Reduktion). P versus NP: Definition 5.1 (NTIME(T(n)), DTIME(T(n))), Definition 5.2 (NSPACE(S(n)), DSPACE(S(n))), Halten, hängen nach n Schritten, Stoppen nach n Schritten, Theorem 5.3 (Bandkompression), Theorem 5.4 (Zeitbeschleunigung), Lemma 5.5 (Wachstumsrate von DTIME, DSPACE), Definition 5.6 (P, NP, PSPACE). Übungsblatt 7 17.01.2011 01:33:14 637 P versus NP 5.1 Die Struktur von PSPACE: Lemma 5.5 (Wachstumsrate von DTIME, DSPACE), Definition 5.6 (P, NP, PSPACE), Sudoku, Theorem 5.7 (Charakterisierung von NP), Theorem 5.8 (Existenz von schwersten Problemen), Definition 5.9 (Polynomial-Zeit-Reduzibilität), Lemma 5.10 (Polynomial-Zeit-Reduktionen) 31.01.2011 01:28:06 479 P versus NP 5.1 Die Struktur von PSPACE: Theorem 5.7 (Charakterisierung von NP). 5.2 Vollständige und harte Probleme: Definition 5.11 (Vollständig, Hart (Schwer)), Theorem 5.12 (NP-vollständige Probleme), Definition 5.13 (co-NP). 5.3 Beispiele: Beispiel 5.14 (NP vollständige Beispiele), Definition 5.15 (Varianten von Hamilton Circle), Definition 5.16 (Maximale Clique: LCliquek), Definition 5.17 (k-colorability: LColork), Definition 5.18 (SAT, k-CNF, k-DNF), Theorem 5.19 (NP-vollständige Probleme), Definition 5.20 (Vertex Cover: LVertexk), Beispiel 5.21 (CNF-SATpol Cliquek), Beispiel 5.22 (hamdir pol Hamundir), Beispiel 5.23 (hamundir pol Hamcostkr) 04.02.2011 01:12:54 494 Anwendungen 6.1 Praktische Bedeutung: Theoretische Komplexität vs. praktische Anwendbarkeit, Compilerbau, Lexikalische Analyse, Syntaxanalyse, Reguläre Ausdrücke, Kleine Automaten. 6.2 Satz von Myhill-Nerode: Definition 6.1, Lemma 6.2, Beispiel 6.3, Theorem 6.4 (Satz von Myhill-Nerode), Beweis. 6.3 Der Minimalautomat: Definition 6.5 (ML, der zu L passende Automat), Äquivalenz, Theorem 6.6 (Minimalität von ML), Beweis
