BuK/IIm20/Vorlesung 7 Lemke

Wiki-Quelltext dieser Seite.

<language>FLACI_c2889grozq3oug</language>
== Kreativaufgabe S. 8 ==

=== Sprache der Turingmaschinenkodierung ===

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

Hier kann man Eingaben testen:

<run id="6096a86351288">
q1q2q3$abc$abc€$q1$€$q2q3$q1abRq2$q2bcLq1$$$
</run>

== Übungsaufgabe S. 15 ==

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

Ein Entwurf eines Algorithmus:

[[Bild:Abc-TM-Algorithmus.jpg]]

Die Implementation mit einem Zustandsdiagramm:

[[Bild:Abc-tm.png]]

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

== Übungsaufgabe S. 18 ==

=== Beweis zur Kontraposition des Reduzierbarkeitssatzes ===

[[Bild:Beweis-mit-Wahrheitstafel.jpg]]

== Die Entscheidungsprobleme als charakteristische Funktionen ==

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

<code id="60969a2e6d1bb">
def chi_LH(kodierung_TM, wort):
	if eval(kodierung_TM, wort) == True or eval(kodierung_TM, wort) == False:
		return True
	else:
		return False
</code>

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

<code id="60969a2e6d255">
def chi_LHepsilon(kodierung_TM):
	epsilon = ''
	if eval(kodierung_TM, epsilon) == True or eval(kodierung_TM, epsilon) == False:
		return True
	else:
		return False
</code>

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

<code id="60969a2e6d2cf">
def chi_LBP(koderierung_TM):
	if eval(kodierung_TM) == True or eval(kodierung_TM) == False:
		return True
	else:
		return False
</code>

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

<code id="60969a2e6d32c">
def chi_Lf(kodierung_TM):
	w = 'blabla'
	f = random_function
	if eval(kodierung_TM, w) == f(w):
		return True
	else:
		return False
</code>

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

<code id="60969a2e6d388">
def chi_Lepsilon(kodierung_TM):
	epsilon = ''
	if eval(kodierung_TM, epsilon) == True:
		return True
	else:
		return False
</code>

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

<code id="60969a2e6d3fc">
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
</code>

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

<code id="60969a2e6d453">
def chi_Lregulaer(kodierung_TM):
	return ist_tm_zu_endlichem_automaten_reduzierbar(kodierung_TM)
</code>

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

<code id="60969a2e6d4a6">
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
</code>