Automaten, Sprachen und Komplexität

Das Fach wird in der PO 2021 nicht mehr angeboten. Stattdessen gibt es „Automaten und formale Sprachen“ im 3. FS und „Berechenbarkeit und Komplexität“ im 4. FS.

• ASK WS 2019/2020

Die Übungen bestehen aus Präsenz- und Bonusaufgaben, von denen die Bonusaufgaben abgegeben werden sollten. Diese erzeugen anteilig 10% Bonuspunkte (prozentual zur maximalen Klausurpunktzahl), was bedeutet, dass man mit 40% der Klausurpunkte und 10% Bonuspunkte ( ~100% Bonusaufgaben richtig) immer noch 50% der Punkte in der Prüfung erhält und evtl. dadurch besteht!
Der Abgabetermin ist der Vorlesung zu entnehmen ( WS19/20: bis 12 Uhr Montag zur Übung oder im Briefkasten vor Z1047 Stand WS 19/20 ).
Präsenzaufgaben dienen der Übung und werden mit den Bonusaufgaben in den Übungsstunden besprochen!

Die Klausur dauerte 2,5h und umfasste insgesamt 150 Punkte.

• 1/3 der Punkte erzielt man durch das aufschreiben von Definitionen, von der jede 2-6 Punkte Wert ist.
• 1/6 der Punkte bekommt man auf NFA/DFA, die Umwandlung zwischen denen, Minimierung.
• Der Rest bestand aus der Anwendung von Algorithmen.

Einige Themen:

• CYK-Algorithmus
• Algorithmus zum Finden von erkennungsäquivalenten Zuständen
• Nichtlösbare Probleme
• Reduktion
• Definition rekusiv aufzählbar
• Definition Loop-Programm
• Definition Myhill-Nerode-Äquivalenz
• Beweis von Nicht-Kontextfreiheit (z.B. mittels Pumping-Lemma für kontextfreie Sprachen)
• Definition PDA
• Erstellung einer Turing-Maschine, um eine Binärzahl zu invertieren und führende Nullen zu entfernen.

Bis auf die Definition wurde kein Beweis mittels Pumping-Lemma gefordert.

Siehe hierzu auch Probeklausur WS15