Zur Startseite der Abteilung Theoretische Informatik

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

Termine

ZeitRaumTermine
Di 15:45-17:15 V47.02 wöchentlich ab 08.04. bis 15.07. außer 10.06. bis 01.07.
Do 14:00-15:30 V47.02 wöchentlich ab 10.04. bis 10.07. außer 12.06. bis 26.06.

Erste Vorlesung: 08.04.

Die Scheinliste sowie die Ergebnisse der Scheinklausur hängen neben Raum 1.101 aus. Bitte informieren Sie sich dort vor der Prüfung, ob Sie die Scheinbedingungen erfüllt haben!!

Folien und voraussichtliche Termine:
Vorl.DatumFolienInhalt
1 08.04. pdf Semesterplanung, Grammatiken: Definitionen und Beispiele
2 10.04. pdf Chomsky-Hierarchie, Wortproblem
3 15.04. pdf Syntaxbäume, Backus-Naur-Form
4 17.04. pdf Reguläre Sprachen: Endliche Automaten, Nichtdet. Automaten (Teil 1)
5 22.04. pdf Nichtdeterministische Automaten (Teil 2)
6 24.04. pdf Reguläre Ausdrücke
7 29.04. pdf Pumping-Lemma und Äquivalenzrelationen
  01.05.   (Feiertag - Keine Vorlesung)
8 06.05. pdf Minimalautomaten, Erkennung durch Monoide, Abschlusseigenschaften
9 08.05. pdf Entscheidbarkeit, Kontextfreie Sprachen: Normalformen (Teil 1)
10 13.05. pdf Normalformen (Teil 2)
11 15.05. pdf Das Pumping-Lemma (bzw. uvwxy-Theorem) für kontextfreie Sprachen
12 20.05. pdf Abschlusseigenschaften, der CYK-Algorithmus
13 22.05. pdf Kellerautomaten (Teil 1)
14 27.05. pdf Kellerautomaten (Teil 2)
  29.05.   (Feiertag - keine Vorlesung)
15 03.06. pdf Determin. kontextfreie Sprachen, Entscheidbarkeit bei kontextfr. Sprachen
16 05.06. pdf Kontextsensitive und Typ-0 Sprachen, Turingmaschinen, VU
      (keine Vorlesung)
17 03.07. pdf LBA, Satz von Kuroda
  08.07.   (keine Vorlesung)
18 10.07. pdf Typ 0 und Turingmaschinen, Satz von Immerman und Szelepcsenyi
  15.07.   SCHEINKLAUSUR
19 17.07. (pdf_alt) Tabellen und Zusammenfassung

Übungsgruppen

GruppeTutorZeitBeginnRaumBesprechung
Blatt 1Blatt 2Blatt 3Blatt 4Blatt 5Blatt 6
1 Weißer Do 11:30-13:00 24.04. 0.457 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
2 Wächter Do 11:30-13:00 24.04. 0.463 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
3 Sauer Do 15:45-17:15 24.04. 0.457 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
4 Weißer Do 15:45-17:15 24.04. 0.463 24.04. 08.05. 22.05. 05.06. 26.06. 10.07.
5 Walter Fr 8:00-9:30 25.04. 0.463 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
6 Weiß Fr 14:00-15:30 25.04. 0.124 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
7 Schnelle Fr 14:00-15:30 25.04. 0.457 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
8 Bühler Fr 14:00-15:30 25.04. 0.463 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
9 Schneider Fr 15:45-17:15 25.04. 0.457 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
10 Bühler Fr 8:00-9:30 25.04. 0.118 25.04. 09.05. 23.05. 06.06. 27.06. 11.07.
11 Walter Fr 8:00-9:30 02.05. 0.463 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
12 Weiß Fr 14:00-15:30 02.05. 0.124 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
13 Schnelle Fr 14:00-15:30 02.05. 0.457 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
14 Bühler Fr 14:00-15:30 02.05. 0.463 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
15 Schneider Fr 15:45-17:15 02.05. 0.457 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
16 Bühler Fr 8:00-9:30 02.05. 0.118 02.05. 16.05. 30.05. 20.06. 04.07. 18.07.
17 Reingruber Di 17:30-19:00 22.04. 0.124 22.04. & 29.04. 06.05. & 13.05. 20.05. & 27.05. 03.06. & 17.06. 24.06. & 01.07. 08.07. & 15.07.
18 Reingruber Mi 17:30-19:00 23.04. 0.124 23.04. & 30.04. 07.05. & 14.05. 21.05. & 28.05. 04.06. & 18.06. 25.06. & 02.07. 09.07. & 16.07.

Übungsblätter

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.