Vorlesung 7 Lemke

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Kreativaufgabe S. 8 1.1 Sprache der Turingmaschinenkodierung 2 Übungsaufgabe S. 15 2.1 Teil der Reduktionsmaschine des Reduktionsalgorithmus, prüft, ob Wort Form uu hat und hinterlässt u 3 Übungsaufgabe S. 18 3.1 Beweis zur Kontraposition des Reduzierbarkeitssatzes 4 Die Entscheidungsprobleme als charakteristische Funktionen

Kreativaufgabe S. 8

Sprache der Turingmaschinenkodierung

Die Definition der formalen Sprache auf FLACI: https://flaci.com/Trozq3oug

Hier kann man Eingaben testen:

q1q2q3$abc$abc€$q1$€$q2q3$q1abRq2$q2bcLq1$$$

ausführen

Übungsaufgabe S. 15

Teil der Reduktionsmaschine des Reduktionsalgorithmus, prüft, ob Wort Form uu hat und hinterlässt u

Ein Entwurf eines Algorithmus:

Die Implementation mit einem Zustandsdiagramm:

Zum Ausprobieren, hier der Link zum Zustandsdiagramm auf FLACI: https://flaci.com/Aiqx00tiz

Übungsaufgabe S. 18

Beweis zur Kontraposition des Reduzierbarkeitssatzes

Die Entscheidungsprobleme als charakteristische Funktionen

$L_H = \{<M>w\ |\ M(w)$ stoppt nach endlicher Zeit$\}$

def chi_LH(kodierung_TM, wort): if eval(kodierung_TM, wort) == True or eval(kodierung_TM, wort) == False: return True else: return False

$L_{H_ε} = \{<M> |\ M(ε)$ stoppt nach endlicher Zeit$\}$

def chi_LHepsilon(kodierung_TM): epsilon = '' if eval(kodierung_TM, epsilon) == True or eval(kodierung_TM, epsilon) == False: return True else: return False

$L_{LBP} = \{<M> |\ M$ hält auf dem (anfangs) leeren Band$\}$

def chi_LBP(koderierung_TM): if eval(kodierung_TM) == True or eval(kodierung_TM) == False: return True else: return False

$L_f = \{<M> |\ M(w ) = f (w )\}$

def chi_Lf(kodierung_TM): w = 'blabla' f = random_function if eval(kodierung_TM, w) == f(w): return True else: return False

$L_ε = \{<M> |\ ε ∈ L(M)\}$

def chi_Lepsilon(kodierung_TM): epsilon = '' if eval(kodierung_TM, epsilon) == True: return True else: return False

$L_∅ = \{<M> |\ L(M) = ∅\}$

def chi_Lleer(kodierung_TM): eingabewortmenge = wortmenge(eingabe_alphabet_aus_kodierung(kodierung_TM)) for w in eingabewortmenge: if eval(kodierung_TM, w) == True: return False else: return True

$L_{reg} = \{<M> |\ L(M)$ ist regulär$\}$

def chi_Lregulaer(kodierung_TM): return ist_tm_zu_endlichem_automaten_reduzierbar(kodierung_TM)

$L_{Σ^∗} = \{<M> |\ L(M) = Σ^∗ \}$

def chi_Ltotal(kodierung_TM): eingabewortmenge = wortmenge(eingabe_alphabet_aus_kodierung(kodierung_TM)) for w in eingabewortmenge: if eval(kodierung_TM, w) == False: return False else: return True