| |
Automatentheorie und Formale Sprachen
Dozent
- Martin Kutrib
Zeit und Raum
- Vorlesung:
- Dienstag, 8-10 Uhr, Hösaal im Mathematischen Institut, Arndtstr. 2
- Mittwoch, 8-10 Uhr, Hösaal im Mathematischen Institut, Arndtstr. 2
- Beginn: 14. April 2009
- Übung:
(Andreas Malcher)
- Dienstag, 12-14 Uhr, Hörsaal 12 des MZVG
- Beginn: 21. April 2009
Prüfung
- Die Zugangsdaten entsprechen jeweils denen des Skripts.
- Evaluation
- Evaluationsergebnisse
- Klausur
- Die Klausur fand am Dienstag, 14.7.2009, von 8.00 bis 10.00 Uhr
im Hörsaal des Mathematischen Instituts, Arndtstr. 2 statt.
- Ergebnisse
- Die Klausuren können vormittags im Sekretariat des Instituts
für Informatik in der Arndtstr. 2, Raum 27, eingesehen werden.
Zielgruppe
Die Veranstaltung richtet sich in erster Linie an Studierende
der Master-Studiengänge Mathematik, des Studiengangs
Lehramt L3 Informatik im fünften oder siebten Semester sowie
der Diplomstudiengänge Mathematik und Physik mit Nebenfach Informatik.
Inhalt
- 1. Grundlegende Notationen und Begriffe
- 2. Sprachen und Grammatiken
- 3. Endliche Automaten und reguläre Sprachen
- 4. Verallgemeinerungen endlicher Automaten
- 5. Kellerautomaten und kontextfreie Sprachen
- 6. Weiteres zur Chomsky-Hierarchie
- 7. (Un)Entscheidbarkeit
Skriptum
- Inhaltsverzeichnis:
PDF (29 kB)
- Kapitel 1:
PDF (82 kB)
- Kapitel 2:
PDF (114 kB)
- Kapitel 3:
PDF (172 kB)
- Kapitel 4:
PDF (152 kB)
- Kapitel 5:
PDF (215 kB)
- Kapitel 6:
PDF (154 kB)
- Kapitel 7:
PDF (136 kB)
Voraussetzungen
- Kenntnisse im Umfang der Veranstaltungen
Grundlagen der Informatik I, II
Literatur
- J. Gruska.
Foundations of Computing.
International Thomson Computer Press 1997.
- J.E. Hopcroft, J.D. Ullman.
Introduction to Automata Theory, Language, and
Computation.
Addison-Wesley 1979.
- A. Salomaa.
Formal Languages.
Academic Press 1973
|