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$$$

Ü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