Formale Sprachen und Automatentheorie

 


Lehrveranstaltungen


 

Formale Sprachen und Automatentheorie


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




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




Allgemeines:

Stundentausch:
Donnerstag, 2.10.03, 14 h: (statt Übung) Vorlesung
(Raum 0401)
Donnerstag, 18.12.03, 13 h: (statt Vorlesung) Übung.
(Raum 0401)

Ab 9.10.03:
Beginn der Vorlesung am DO: 13:00
Beginn der Übungsstunde: 14:00


Nächste Sprechstunde zu GThI03/FSA03:
Di, 7.9.04, 15:00, Geb. 41/400, voraussichtlich Raum 1414;
Anmeldung per Email (zur Abschätzung von Zeit- und Raumbedarf) bis 6.9.04 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 - 12 Folien 13 - 16 Folien 17 - 20
Folien 21 - 24 Folien 25 - 28 Spaltungsalgorithmus zur Minimierung Folien 29 - 32
Folien 33 - 36 Folien 37 - 44 Folien 45 - 52 CYK
Folien 53 - 64










Übungen:

Das erste Übungsblatt wird am 2.10. ausgegeben. Die erste Übungsstunde findet am 9.10. statt.


Gruppe 1 Elbl Raum 0401
Gruppe 2 Iwan Raum 36/01242



 

Übungsblatt 1 Übungsblatt 2 und 3 Übungsblatt 4
Übungsblatt 5 Übungsblatt 6 Übungsblatt 7
Übungsblatt 8 Übungsblatt 9 Übungsblatt 10
Übungsblatt 11/12









DVP-Klausur Januar 2004 DVP-Klausur April 2004

 
 



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