"
helfen und aufkommende Fragen beantworten. Außerdem wird auch auf Fragen, die die Bearbeitung der Übungsaufgaben betreffen, eingegangen.
| Folien der 1. Woche | Operationen auf Sprachen, DFAs |
| Folien der 2. Woche | NFAs, Produktautomat, NFA->DFA, reguläre Ausdrücke |
| Folien der 3. Woche | Relationen und ihre Eigenschaften |
| Folien der 4. Woche | Ordnungs- und Äquivalenzrelationen, DFA-Minimierung, Graphisomorphie |
| Folien der 5. Woche | Pumping-Lemma, Myhill-Nerode-Relation, 2. Minimierungs Beispiel | Neuer Foliensatz, 2. Beispiel für eine Minimierung eingefügt! Fehler bei der Bestimmung einer Pumpingzahl beseitigt! |
| Folien der 6. Woche | Reguläre Grammatiken, Umwandlung: Reguläre Grammatik ↔ Endlicher Automat |
| Folien der 7. Woche | Kontextfreie Sprachen und PDAs |
| Foliensatz 7.5 | PDAs, Umwandlung: Kontextfreie Grammatik → PDA |
| Folien der 8. Woche | Umwandlung: PDA → Kontextfreie Grammatik, Kontextsensitive Grammatik, LBA, Bottom-Up-Parser |
| Folien der 9. Woche | Definitionen (Semi-)Entscheidbarkeit, Beispiele für Berechenbarkeit |
| Folien der 10. Woche | (M)PCP und das Wortproblem für Typ-0-Grammatiken | Lösungen für die gegebene PCP-Instanz |
| Sonderfolien: Satz von Rice | Einige Beispiele zum Satz von Rice und dessen Anwendbarkeit |
| Folien der 11. Woche | Kodierungen, LOOP, WHILE und GOTO | C-Code für GOTO- und LOOP-Programm |
| Folien der 12. Woche | Übungsaufgaben zu Landau-Notation und Erfüllbarkeit |
| Folien der 13. Woche | Übungsaufgabe zu Graphparametern |
