Seminar: Automatentheorie
WiSe12/13
Organisatorisches
Dozentin: Wiebke Petersen
Sitzung: Mo. 16.30-18.00; 25.22.HS 5G
Sprechstunde: Di. 16:30-17:30; 23.21.04.45;
Telefon: 81-15295
Kurslektüre
- Rolf Socher: Theoretische Grundlagen der Informatik. Hanser Fachbuchverlag, 2008 (3. Auflage).Dieses Buch kann beispielsweise beim Stern-Verlag auf dem Campus (gegenüber vom Kiosk) gekauft werden (dort ist das Buch vorrätig).
- Handout zum Kurs (wöchentlich wachsend)
- Lösungen zum Ziege-Wolf-Kohlkopfproblem: (Übergangsnetz von Anika Westburg) (von Anika Westburg für AtoCC) (Prolog von Wiebke Petersen) (DEA in Prolog von Wiebke Petersen) (DEA für Machines von Wiebke Petersen)
Literaturempfehlung
- Dirk W. Hoffmann (2. Auflage, 2011): Theoretische Informatik. Hanser Fachbuchverlag
- Uwe Schöning (5. Aufl., 2008): Theoretische Informatik - kurzgefasst. Spektrum.
- Barbara H. Partee et al.: Mathematical Methods in Linguistics, Part E. Dordrecht et al.: Kluwer Acad. Publ., 1990.
- Ralf Klabunde: Formale Grundlagen der Linguistik. Tübingen: Gunter Narr Verlag, 1998. (Errata)
hilfreiche Software
- Exorciser ; Exorciser-Homepage
- JFLAP
- Regex Tester
- noch ein Regex Tester
- und noch ein Regex Tester
- SWI Prolog
Klausur, Probeklausur und Pencasts
- Ich werde leider nicht vor dem 22.4.2013 dazu kommen, mit der Korrektur der Klausur zu beginnen. Ich peile an, diese spätestens am 3.5. abgeschlossen zu haben, aufgrund des Umzugs meines Büros kann es aber zu weiteren Verzögerungen kommen. Die Ergebnisse werde ich auf dieser Seite zur Verfügung stellen.
- Zur Vorbereitung auf die Klausur, steht ihnen eine Probeklausur mit Lösungen zur Verfügung.
- Zusätzlich habe ich für einige Aufgaben sogenannte Pencasts erstellt, zu deren Betrachtung sie einen aktuellen Adobe Reader benötigen Aufgabe A1 und A2, Aufgabe A3, Aufgabe A4, Aufgabe B1 und Aufgabe B2
Sitzungen
| Datum | Thema | Material |
|---|---|---|
| 08.10.2012 | Vorbesprechung | |
| 15.10.2012 | offiziell vorlesungsfrei: Eröffnung des akademischen Jahres | Einführungsfolien | 22.10.2012 | Deterministische endliche Automaten | Socher, Kapitel 2 (bitte lesen Sie dieses Kapitel vor der Sitzung) | 29.10.2012 | Nichtdeterministische endliche Automaten |
|
05.11.2012 | Reguläre Ausdrücke | Socher, Kapitel 3 (bitte lesen Sie dieses Kapitel vor der Sitzung) | 12.11.2012 | Pumpinglemma für reguläre Sprachen, Satz von Myhill-Nerode | Socher, Kapitel 3 | 19.11.2012 | Grammatiken, CYK-Parser | Socher, Kapitel 4 | 26.11.2012 | Kellerautomaten | Socher, Kapitel 4 | 03.12.2012 | Typ1- und Typ0-Grammatiken, Chomsky-Hierarchie, Überabzählbarkeit | Socher, Kapitel 5 (bitte lesen Sie dieses Kapitel vor der Sitzung) | 10.12.2012 | Turing-Maschinen, LBA, Turing-Berechenbarkeit | Socher, Kapitel 5 | 17.12.2012 | universelle Turingmaschine, Churchsche These | Socher, Kapitel 5 | 07.01.2013 | Entscheidbarkeit | Socher, Kapitel 6 | 14.01.2013 | Entscheidbarkeit, Reduktionsbeweise | Socher, Kapitel 6 | 21.01.2013 | Reduktionsbeweise, Satz von Rice | Socher, Kapitel 6 | 28.01.2013 | Socher, Kapitel 7 | Komplexitätstheorie, NP-Vollständigkeit | 05.04.2013 | Klausur, 10:30 Uhr. Ort: 23.21. Hörsaal 3H Probeklausur für Übungszwecke mit Lösungen (weitere Lösungen werden nachgereicht) |
zusätzliche Materialien
Ãœbungsaufgaben
- Hinweise für die Anwendung des Pumpinglemmas für reguläre Sprachen
- zusätzliche Übungsaufgaben zu regulären Sprachen ( Musterlösung zur Aufgabe 9 )
- Beispiel für CNF (aus Hoffmann 2011)
- Mathe-Prisma Modul zu Turingmaschinen (link)
- Probeklausur für Übungszwecke mit Lösungen
- Lösungen zum Ziege-Wolf-Kohlkopfproblem:
Weitere Materialien (von Gruppen aus vergangenen Semestern erstellt)
- Konstruktion eines deterministischen Automatens aus einem nichtdeterministischen nach Klabunde 1998
- effziente Konstruktion eines deterministischen Automatens aus einem nichtdeterministischen
- Eliminierung von ε-Ãœbergängen und Abschlusseigenschaften von regulären Sprachen