Formale Sprachen und Berechenbarkeit Seminar
Dozent:innen: Dr. rer. nat. Markus BlumenstockKurzname: 08.079.24616
Kurs-Nr.: 08.079.24616
Kurstyp: Seminar
Voraussetzungen / Organisatorisches
Es wird erwartet, dass die Klausur zu "Formale Sprachen und Berechenbarkeit" bestanden wurde.Das Seminar findet während der Vorlesungszeit statt, der Termin wird durch eine Umfrage festgelegt.
Vorbesprechung: 2. September, 10:00 in BBB https://bbb.rlp.net/rooms/v0m-g2u-lsm-cmh/join
Anwesenheitspflicht
Es besteht Anwesenheitspflicht.Inhalt
Mögliche Themen sind u. a.:- (Nicht)-Kontextfreiheit von natürlichen Sprachen
- Ogdens Lemma (allgemeineres PL für kf. Sprachen)
- Jaffes Pumping Lemma (notwendiges und hinreichendes PL für reguläre Sprachen)
- LR-Parser (deterministisch kf. Sprachen)
- Unentscheidbarkeitsresultate für Grammatiken
- Unentscheidbarkeit von Wang-Parkettierungen ("Affenpuzzle" im Foyer)
- Kleenes Rekursionssatz
- Algorithmische Informationstheorie, Kolmogorov-Komplexität
Termine
| Datum (Wochentag) | Zeit | Ort |
|---|---|---|
| 08.11.2024 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 15.11.2024 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 22.11.2024 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 29.11.2024 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 06.12.2024 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 13.12.2024 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 20.12.2024 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 10.01.2025 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 17.01.2025 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 24.01.2025 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 31.01.2025 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |
| 07.02.2025 (Freitag) | 12:15 - 13:45 | 04 426 2413 - Neubau Physik/Mathematik |