Theoretische Informatik

Aufzählbarkeit
Sei g : N → N berechenbar mit g(0) = 0. Gesucht ist eine totale, berechenbare Funktion h : N → N mit Wh = Dg. Definieren Sie h und weisen Sie die geforderten Eigenschaften nach!

Äquivalenz von DEAs
Testen Sie die Äquivalenz folgender DEAs mit dem Verfahren auf Skriptseite 227 und geben Sie die entstehende Tabelle an. [Graph fehlt in dieser Online-Edition]

Minimierung von DEAs
Minimieren Sie folgenden DEA. (gefordert: Tabelle unterscheidbarer Zustände + Äquivalenzklassen + Zeichnung des DEA) [Graph fehlt in dieser Online-Edition]

Python-Programm für DEA-Äquivalenztest
Schreiben Sie ein Python-Programm für den Äquivalenztest von DEAs. Verwenden Sie das Verfahren auf Skriptseite 227.

Python-Programm zur DEA-Minimierung
Schreiben Sie ein Python-Programm zur Minimierung von DEAs. Verwenden Sie das Verfahren auf Seite 232.

Python-Programm zur Umrechnung von NEAs in reguläre Ausdrücke
Schreiben Sie ein Python-Programm, das mit der Methode aus Satz 3.28 NEAs in reguläre Ausdrücke umwandelt.

Halt nach gerader Schrittzahl
Sei M₀,M₁,... eine Gödelisierung der RAMs. Zeigen Sie die Unentscheidbarkeit der Menge
A = {x ∈ N | Mx(x) hält nach einer geraden Anzahl von Schritten}.