Vorlesung 7 Lemke

Aus ProgrammingWiki

< BuK < IIm20

Archivierte Version vom 2021-05-08T14:03:26+00:00. Aktuelle Version

Inhaltsverzeichnis

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

Ü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:

Ü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

Vorlesung 7 Lemke

Inhaltsverzeichnis

Übungsaufgabe S. 15

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

Übungsaufgabe S. 18

Beweis zur Kontraposition des Reduzierbarkeitssatzes

Die Entscheidungsprobleme als charakteristische Funktionen

Suche