Formale Sprachen

Dozent:innen: Univ.-Prof. Dr. Friederike Schmid
Kurzname: 08.079.05050
Kurs-Nr.: 08.079.050-LING
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. Einführung 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. Churchs 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 Audi Max
    26.04.2022 (Dienstag) 10:00 - 12:00 Audi Max
    03.05.2022 (Dienstag) 10:00 - 12:00 Audi Max
    10.05.2022 (Dienstag) 10:00 - 12:00 Audi Max
    17.05.2022 (Dienstag) 10:00 - 12:00 Audi Max
    24.05.2022 (Dienstag) 10:00 - 12:00 Audi Max
    31.05.2022 (Dienstag) 10:00 - 12:00 Audi Max
    07.06.2022 (Dienstag) 10:00 - 12:00 Audi Max
    14.06.2022 (Dienstag) 10:00 - 12:00 Audi Max
    21.06.2022 (Dienstag) 10:00 - 12:00 Audi Max
    28.06.2022 (Dienstag) 10:00 - 12:00 Audi Max
    05.07.2022 (Dienstag) 10:00 - 12:00 Audi Max
    12.07.2022 (Dienstag) 10:00 - 12:00 Audi Max
    19.07.2022 (Dienstag) 10:00 - 12:00 Audi Max