Not logged in. · Lost password · Register

Cerox
Member since Jan 2014
29 posts
Subject: 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> | M, eine deterministische 1-Band Turingmaschine, gestartet mit leerem Band, hält.}

b
L2b = {<M> | 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:
1. Eingabe sei y
2. Falls y = #101
3.   laufe unendlich
4. sonst
5.   starte <M>
6.   halte

"=>" x ∈ H0  => x = <M>
                   => F<M> hält
                   => <F<M>>#101 ∈ L2b
"<=" x !∈ H0 => x != <M> => f(x) = 0
                   => x = <M> => <F<M>> 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
[Image: http://i.imgur.com/Rddqfh1.png]
Anmerkung: Zustand 2 ist terminierend
a Welche Sprache L1 akzeptiert der Automat?
   L1 = { w in {a,b,c}* | w enthält b}

b [Image: http://i.imgur.com/Wh0H1Ws.png]

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

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.
This post was edited 5 times, last on 2015-07-26, 16:12 by Cerox.
DerTyp
Member since Feb 2016
2 posts
Aufgabe 1c)

Stimmt nicht. Gegenbeispiel: L_1 = H und L_2 = Sigma*
ulfHorst
Member since Nov 2017
1 post
In reply to post #1
2: Die Reduktion ist in jedem Fall falsch: Deine TM F hält immer für ein x nicht (x = 101), egal was <M> ist.
Außerdem funktioniert nur Hquer <= L, nicht H0 <= L.
4.a Sprache: {a^n*b^m*c^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
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen