Formale Sprachen und Automatentheorie

Formale Sprachen und Automatentheorie


Allgemeines/Ankündigungen Kurzbeschreibung
Material zur Vorlesung Übungsblätter Literatur




Die Seite mit Material zu FSA-HT01 ist nun hier.

Die Seite mit Material zu FSA-HT03 ist nun hier.




Allgemeines:


Stundentausch:
Mittwoch, 6.10.04, 11 h: (statt Übung) Vorlesung
(Raum 0301)
Mittwoch, 15.12.04, 10 h: (statt Vorlesung) Übung.
(verlegt auf: DO 16.12.04, 8-10)

MI künftig: Beginn der Vorlesung 10:10, Beginn der Übung 11:05




Nächste Sprechstunde zu GThI04/FSA04:
Mo, 11.4.05, 15 Uhr, voraussichtlich Raum 41 / 1414
Anmeldung per Email (zur Abschätzung von Zeit- und Raumbedarf) bis 8.4.05 erforderlich!




Material zur Vorlesung:

Hier sind künftig die in der Vorlesung verwendeten Folien zu finden.
Diese allein ergeben noch kein vollständiges Skript!!!!

Folien 1 - 8 Folien 9 - 16 Folien 17 - 23 Folien 24 - 27 Spaltungsalgorithmus zur Minimierung
Folien 28 - 31 Folien 32 - 39 Folien 40 - 43 Folien 44 - 47 Folien 48 - 51
CYK Folien 52 - 55 Folien 56 - 64







Übungen:


Das erste Übungsblatt wird am 6.10. ausgegeben. Die erste Übungsstunde findet am 13.10. statt.


Gruppe 1 Polanski Raum 0301
Gruppe 2 Iwan Raum 2401


Hier sind künftig die Übungsblätter zu finden (Ausgabe jeweils MI).
 
Übungsblatt 1 Übungsblatt 2 Übungsblatt 3
Übungsblatt 4 Übungsblatt 5 Übungsblatt 6
Übungsblatt 7 Übungsblatt 8 Übungsblatt 9
Korrektur: In Aufgabe 20 ist die Produktion S -> e zu ergänzen.
Übungsblatt 10/11

Zur Wiederholung:
GThI/FSA - 1 GThI/FSA - 2 siehe auch: GThI-Seite













DVP-Klausur Januar 2005

 
 

Literatur:


  • Schöning. Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag, 3. Auflage 1997.
  • Hopcroft, Motwani, Ullman. Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Pearson Studium, 2. Auflage, 2002.
  • Hopcroft, Ullman. Introduction to automata theory, languages and computation. Addison-Wesley 1979.





Kurzbeschreibung:


Gegenstand dieser Vorlesung ist die Theorie der Chomsky-Sprachklassen und der zugehörigen Automatenbegriffe, wobei der Schwerpunkt auf regulären und kontextfreien Sprachen liegt.
Inhalte sind insbesondere:
  • Die Hierarchie der Chomsky-Sprachklassen: Grammatikklassen und Akzeptoren, Abschlußeigenschaften
  • Reguläre Sprachen: Chomsky-3-Grammatiken, deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Konstruktion von Minimalautomaten, Satz von Myhill-Nerode, Pumping-Lemma für reguläre Sprachen, Entscheidbarkeitsfragen
  • Kontextfreie Sprachen: Chomsky-2-Grammatiken, Kellerautomaten, Umformungen für Grammatiken und Normalformen (insbesondere Chomsky-Normalform und Greibach-Normalform), Pumping-Lemma für kontextfreie Sprachen, CYK-Algorithmus, Entscheidbarkeitsfragen




Weitere Informationen zu Lehrveranstaltungen unseres Instituts

Institut für Theoretische Informatik und Mathematik 


Birgit Elbl