Formale Sprachen und Berechenbarkeit

Dozent:innen: Univ.-Prof. Dr. Friederike Schmid
Kurs-Nr.: 08.079.050
Kurstyp: Vorlesung/Übung

Empfohlene Literatur


  1. Dirk Hoffmann: Theoretische Informatik
  2. Asteroth/Baier: Theoretische Informatik
  3. Schöning: Theoretische Informatik - kurz gefaßt
  4. Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie
  5. Priese, Erk: Theoretische Informatik - Eine umfassende Einführung

Inhalt


  1. Mathematische Grundlagen
  2. Formale Sprachen
    3. [list]
  3. Reguläre Sprachen und endliche Automaten
  4. Kontextfreie Sprachen und Kellerautomaten

  • Berechenbarkeit

    1. Turing-Maschine als Berechnungsmodell
    2. Weitere Berechnungsmodelle und Äquivalenz zur TM
    3. Church’s-These: TM-Berechenbarkeit stimmt mit der intuitiven Definition von Berechenbarkeit überein
    4. Unentscheidbare Probleme

    [/list]

    Termine

    Datum (Wochentag) Zeit Ort
    19.04.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    26.04.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    03.05.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    10.05.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    17.05.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    24.05.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    31.05.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    07.06.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    14.06.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    21.06.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    28.06.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    05.07.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    12.07.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I
    19.07.2022 (Dienstag) 10:00 - 12:00 00 151 Audi Max
    1312 - Aulagebäude/Mensa I