Automaten und Sprachen

Prüfungsvorbereitung

8 Aufgaben

• Kapitel 3: etwas reguläres und etwas nicht reguläres (Pumping Lemma)
• Kapitel 4: etwas kontextfreies und etwas nicht kontextfreies (Pumping Lemma)
• Kapitel 5: etwas über Turing-Maschinen
• Kapitel 6: etwas nicht entscheidbares (Reduktion oder Satz von Rice)
• Kapitel 7: etwas in NP (Verifizierer) und etwas NP-vollständiges (polynomielle Reduktion auf ein bekanntermassen NP-vollständiges Vergleichsproblem).