Formale Methoden 2
VO 2 + UE1 SS 2005 LVA 703001 + 703002
Beschreibung
Die Vorlesung führt die Grundlagen der formalen Sprachen ein und skizziert die Grundlagen der Komplexitätstheorie.Übersicht
| Woche 1: | Automaten, Grammatiken, reguläre Ausdrücke |
| Woche 2: | Formales Beweien, Induktionsbeweise |
| Woche 3: | Wörter, Sprachen, Reguläre Ausdrücke, Grammatiken |
| Woche 4: | Reguläre Ausdrücke in Unix, lex, Pattern matching |
| Woche 5: | reguläre Sprachen und Gramatiken, endliche Automaten (EA) |
| Woche 6: | reguläre Ausdrücke, deterministische EA |
| Woche 7: | Pumping Lemma für reguläre Sprachen, Abschlusseigenschaften |
| Woche 8: | Entscheidungsproblem für reg. Sprachen, Minimisierung |
| Woche 9: | kontext-freie Sprachen und Grammatiken, Kellerautomaten (KA) |
| Woche 10: | deterministische KA |
| Woche 11: | Chomsky Normal Form |
| Woche 12: | Turingmachinen (TM), unbeschränkte Sprachen |
| Woche 13: | Konstruktion von TM |
| Woche 14: | Entscheidbarkeit und Aufzählbarkeit |
| Woche 15: | P vs. NP |
Literatur
Zur Vorlesung exisitiert ein Skript, als zusätzliche Lektüre empfehle ich wärmstens das BuchHopcroft et al., Introductin to Automata Theory, Languages, and Computation, Pearson Studium (Oktober 2002)