Nächstes Semester

Formale Sprachen

Dozent:innen: Univ.-Prof. Dr. Friederike Schmid; Dr. rer. nat. Markus Blumenstock
Kurzname: 08.079.05050
Kurs-Nr.: 08.079.050-LING
Kurstyp: Vorlesung/Übung
Format: online

Voraussetzungen / Organisatorisches

Die Veranstaltung findet digital in MS Teams statt. Bitte installieren Sie MS Teams und treten dem Team "Formale Sprachen und Berechenbarkeit SS21" mit dem Teamcode 1g4zypl bei.

Digitale Lehre

Der Übungsbetrieb findet digital über MS Teams statt (Beitrittscode 1g4zypl). Alle weiteren Informationen, zum Beispiel wie die Vorlesung stattfindet, finden Sie dort.

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
   
[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]

Zusätzliche Informationen

keine

Termine

Datum (Wochentag)	Zeit	Ort
13.04.2021 (Dienstag)	10:00 - 12:00
20.04.2021 (Dienstag)	10:00 - 12:00
27.04.2021 (Dienstag)	10:00 - 12:00
04.05.2021 (Dienstag)	10:00 - 12:00
11.05.2021 (Dienstag)	10:00 - 12:00
18.05.2021 (Dienstag)	10:00 - 12:00
25.05.2021 (Dienstag)	10:00 - 12:00
01.06.2021 (Dienstag)	10:00 - 12:00
08.06.2021 (Dienstag)	10:00 - 12:00
15.06.2021 (Dienstag)	10:00 - 12:00
22.06.2021 (Dienstag)	10:00 - 12:00
29.06.2021 (Dienstag)	10:00 - 12:00
06.07.2021 (Dienstag)	10:00 - 12:00
13.07.2021 (Dienstag)	10:00 - 12:00