Zur Startseite der Abteilung Theoretische Informatik

Theoretische Grundlagen der Informatik: Formale Sprachen und Automatentheorie (SS 2013)

Termine

ZeitRaumTermine
Di 11:30-13:00 V47.02 wöchentlich ab 9.04. bis 02.07. außer am 28.05.
Do 14:00–15:30 V47.02 wöchentlich ab 11.04. bis 27.06. außer am 02.05.

 

Bitte beachten:

Am Dienstag, dem 2. Juli findet die letzte Vorlesung statt.

Folien:
Vorl.DatumFolienInhalt
1 09.04.  (pdf) Semesterplanung, Grammatiken: Definitionen und Beispiele 
2 11.04.  (pdf) Chomsky-Hierarchie, Wortproblem
3 16.04.  (pdf) Syntaxbäume, Backus-Naur-Form
4 18.04.  (pdf) Reguläre Sprachen: Endliche Automaten, Nichtdeterministische Automaten (Teil 1)
5 23.04.  (pdf) Nichtdeterministische Automaten (Teil 2)
6 25.04.  (pdf) Reguläre Ausdrücke, das Pumping-Lemma
7 30.04.  (pdf) Äquivalenzrelationen und Minimalautomaten
  02.05.   (Keine Vorlesung)
8 07.05.  (pdf) Erkennung durch Monoide, Abschlusseigenschaften, Entscheidbarkeit
  09.05.   (Feiertag - keine Vorlesung)
9 14.05.  (pdf) Kontextfreie Sprachen: Normalformen (Teil 1)
10 16.05.  (pdf) Normalformen (Teil 2)
  28.05.   (Keine Vorlesung)
  30.05.   (Feiertag - keine Vorlesung)
11 04.06.  (pdf) Das Pumping-Lemma (bzw. uvwxy-Theorem) für kontextfreie Sprachen
12 06.06.  (pdf) Abschlusseigenschaften, der CYK-Algorithmus
13 11.06.  (pdf) Kellerautomaten (Teil 1)
14 13.06.  (pdf) Kellerautomaten (Teil 2)
15 18.06.  (pdf) Determin. kontextfreie Sprachen, Entscheidbarkeit bei kontextfr. Sprachen
16 20.06.  (pdf) Kontextsensitive und Typ-0 Sprachen, Turingmaschinen, LBA
17 25.06.  (pdf) Satz von Kuroda
18 27.06.  (pdf) Typ 0 und Turingmaschinen, Satz von Immerman und Szelepcsenyi
19 02.07.  (pdf) Tabellen und Zusammenfassung

Übungsgruppen

GruppeTutorZeitBeginnRaumBesprechung
Blatt 1Blatt 2Blatt 3Blatt 4Blatt 5Blatt 6
1 M. Schneider Di 17:30-19:00 23.04. 0.363 23.04. 07.05. 28.05. 11.06. 25.06. 09.07.
2 T. Walter Mo 14:00-15:30 22.04. 0.453 22.04. 06.05. 27.05. 10.06. 24.06. 08.07.
3 V. Kalach Di 9:45-11:15 23.04. 0.124 23.04. 07.05. 28.05. 11.06. 25.06. 09.07.
4 P. Wagner Di 9:45-11:15 23.04. 0.463 23.04. 07.05. 28.05. 11.06. 25.06. 09.07.
5 M. Reingruber Di 15:45-17:15 23.04. 0.108 23.04. 07.05. 28.05. 11.06. 25.06. 09.07.
6 C. Weisser

Di 15:45-17:15

23.04. 0.124 23.04. 07.05. 28.05. 11.06. 25.06. 09.07.
7 A. Bühler Mi 15:45-17:15 24.04. 0.124 24.04. 08.05. 29.05. 12.06. 26.06. 10.07.
8 M. Schneider Di 17:30-19:00 30.04. 0.363 30.04. 14.05. 04.06. 18.06. 02.07. 16.07.
9 M. Reingruber Mo 14:00-15:30 29.04. 0.453 29.04. 13.05. 03.06. 17.06. 01.07. 15.07.
10 V. Kalach Di 9:45-11:15 30.04. 0.124 30.04. 14.05. 04.06. 18.06. 02.07. 16.07.
11 P. Wagner Di 9:45-11:15 30.04. 0.463 30.04. 14.05. 04.06. 18.06. 02.07. 16.07.
12 M. Reingruber Di 15:45-17:15 30.04. 0.108 30.04. 14.05. 04.06. 18.06. 02.07. 16.07.
13 C. Weisser Di 15:45-17:15 30.04. 0.124 30.04. 14.05. 04.06. 18.06. 02.07. 16.07.
14 A. Bühler Mi 15:45-17:15 30.04.* 0.124 30.04.* 15.05. 05.06. 19.06. 03.07. 17.07.

*Dieser Termin findet wegen des Feiertags am Dienstag, den 30.04. um 8:00 statt.

Übungsblätter

Scheinkriterien

  • Sie müssen jeweils zwei der Aufgaben schriftlich abgeben. Wollen Sie mehr als zwei Aufgaben kontrolliert haben, so kennzeichnen Sie eindeutig die zwei Aufgaben, die bewertet werden sollen.
  • Einen Schein erhält, wer mit den gewählten Hausübungen mindestens 50% der maximal zu erreichenden Punkte erhält und aktive Teilnahme in den Übungsgruppen zeigt. Die aktive Teilnahme beinhaltet das Votieren von mindestens einer zusätzlichen Aufgabe pro Übungsblatt (Ausnahmen bei Krankheit etc. sind mit Ihrem Tutor abzusprechen).

Hinweis: Um an der Modulprüfung "Theoretische Grundlagen der Informatik" teilzunehmen benötigen Sie einen Übungsschein in "Logik und Diskrete Strukturen" oder in "Formale Sprachen und Automatentheorie".

Literatur

  • Uwe Schöning: Theoretische Informatik – kurzgefasst, 5. Auflage, Spektrum, 2008. (Die ältere Auflage von 2000 tut's auch!)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley, 2002.