Aufgabenstellung im Thread
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Lösungsversuch SS 14
Hallo,
ich habe mich mal (, mit einem Freund zusammen) an einem Lösungsversuch vom SS14 versucht.
Aufg1
a Es gibt eine kontextfreie Sprache L über dem Alphabet Σ, so dass das Komplement von L, also die Sprache Σ*\L, unentscheidbar ist.
Stimmt nicht.
Das Komplement einer kontextfreien Sprache L bildet eine kontextsensitive Sprache L’, welche widerum entscheidbar ist.
b Ist L eine rguläre Sprache, so hat L die kontextfreie Pumpeigenschaft
Stimmt.
Die reguläre Pumpeigenschaft ist eine Teilmenge der kontextfreien Pumpeigenschaft. Wird bei der kontextfreien Pumpeigenschaft bspw. u,v = Epsilon, oder x,y = Epsilon gesetzt, erhält man die Anforderungen der regulären Pumpeigenschaft. Jedes Wort einer regulären Sprache kann somit durch die kontextfreie Pumpeigenschaft abgebildet werden.
c Für jede unentscheidbare Sprache L1 gilt: Ist L2 eine echte Obermenge von L1, dann ist L2 ebenfalls unentscheidbar.
Stimmt.
Sei L eine unentscheidbare Sprache. Somit ist jede echte Teilmenge von L (=> L’), ebenfalls unentscheidbar. Folglich ist, wenn L1 eine echte Teilmenge von L2 ist, L2 ebenfalls unentscheidbar.
Aufg2
a H0 := { | M, eine deterministische 1-Band Turingmaschine, gestartet mit leerem Band, hält.}
b
L2b = { | M ist eine deterministische 1-Band Turingmaschine, und es gibt genau ein z ∈ {0,1}*, so dass M gestartet mit z NICHT hält}
zu zeigen: H0 <= L2b
{ <F<M>>#101 falls x=<M>
f(x) = { 0 sonst
f ist total und berechenbar.
F:
- Eingabe sei y
- Falls y = #101
- laufe unendlich
- sonst
- starte
- halte
“=>” x ∈ H0 => x =
=> F hält
=> <F>#101 ∈ L2b
“<=” x !∈ H0 => x != => f(x) = 0
=> x = => <F> hält nicht ==> Widerspruch, x !∈ L2b
Da H0 unentscheidbar, ist auch L2b unentscheidbar.
Aufg 3
a Definieren sie die kontextfreie Pumpeigenschaft
( A sei hier umgedrehtes A und E umgedrehtes E)
AL ∈ L2(Chomsky2).En ∈ Natürlichen Zahlen.Az ∈ L.|z| >= n. Euvwxy, z = uvwxy =>
i) |vx| >= 1
ii) |vwx| <= n
iii) Ai ∈ Natürlichen Zahlen mit 0. z = uv^iwx^iy ∈ L
b Zeigen sie direkt durch Anwendung der Definition der kontextfreien Pumpeigenschaft, dass die Sprache L3b = { 0^l 1^k | k,l ∈ Natürliche Zahlen, 2 < k < l} die kontextfreie Pumpeigenschaft besitzt. (=> k ist min. 3, l min. 4)
Fall 1: o=k(=3), p >= 1
n=9,
u = 0^o
v = 0
w = 1^(o+p)
x = 1
y = Epsilon
Fall 2: o=k, p=1
n=8,
u=0^o
v=Epsilon
w=1^(o+p)
x=1
y=Epsilon
c Zeigen sie direkt durch Anwendung der Definition der kontextfreien Pumpeigenschaft, dass die Sprache L3b = { 0^l 1^k 
^m | k,l,m ∈ Natürliche Zahlen, 2 < k < l < m} die kontextfreie Pumpeigenschaft NICHT besitzt.
Hier müsste zu zeigen sein, dass wenn man bspw nur 0en, oder 0en & 1en pumpt, das entstehende Wort nicht mehr Element der Sprache von L3b ist.
Wie das Formal zu formulieren ist, weiß ich leider nicht so recht…
Aufg 4
Anmerkung: Zustand 2 ist terminierend
a Welche Sprache L1 akzeptiert der Automat?
L1 = { w in {a,b,c}* | w enthält b}
b 
c Sei L = {0^l 1^l | l ∈ Natürliche Zahlen}.
Jemand behauptet, einen DEA A mit L = L(A) konstruiert zu haben. A soll n Zustände besitzen.
Geben sie in Abhängigkeit von n ein Wort z ∈ L an, mit folgender Eigenschaft:
Aus einer akzeptierenden Rechnung von A für z, können Sie Wörter z konstruieren mit der Eigenschaft:
A akzeptiert ^z
^z !∈ L
Zeigen Sie, dass z die genannte Eigenschaft beseitzt.
Keine Ahnung....
Aufg 5
µ Rekursion => Vielleicht nächstes Semester 
Aufg 6
a Beschreibe Definition xy formal…
b Aus der Vorlesung kenne Sie das NP-vollständige Knotenüberdeckungsproblem, Vertex Cover VC :={<G,k> | G ist ein Graph, welcher eine Knotenüberdeckung der Größe k besitzt.}.
bin(a) bezeichne die Binärdarstellung der natürlichen Zahlen a. Sei:
EndeKlein = {bin(a1)#…#bin(an) | n >= 2, an < ai für alle i ∈ {1,…n-1}}
Zeigen Sie: EndeKlein <=p VC
Hinweise: Vergessen sie nicht, die Laufzeit der Berechnung der Reduktion zu begründen.
c Angenommen P = NP. Zeigen Sie, dass EndeKlein dann BP-Vollständig ist, indem sie zeigen: VC <=p Endeklein
Begründen sie insbesondere durch Hinweis auf die Definition des Begriffs, warum EndeKlein damit NP-vollständig ist.
Aufgabe 1c)
Stimmt nicht. Gegenbeispiel: L_1 = H und L_2 = Sigma*
2: Die Reduktion ist in jedem Fall falsch: Deine TM F hält immer für ein x nicht (x = 101), egal was ist.
Außerdem funktioniert nur Hquer <= L, nicht H0 <= L.
4.a Sprache: {a^nb^mc^k | n, k >= 0, m > 0}
4.b : {0, 1} -b-> {1, 2} -c-> {2}
{0, 1} hat a-Pfeil zu sich selbst, {1, 2} b-Pfeil “”, {2} c-Pfeil
6: Offensichtlich