TU Wien:Theoretische Informatik und Logik VU (Fermüller)/Prüfung 2021-04-12 Lösungsvorschlag

Aufgabe 1 (8 Punkte)

[erster Lösungsversuch: Wenn er richtig ist diesen Satz löschen, ansonsten bitte verbessern]

1) Wort wählen = b^maab^m --> |w| > m
2) --> |xy| < m --> |xy| kann nur aus Symbolen b bestehen
3) Wähle ein i: i = 2
4) --> b^m+|y|aab^m
5) --> weil |y|>0 --> |p|=|q| nicht mehr gilt
--> Wort nicht in Sprache
--> nicht regulär

Aufgabe 2 (4 + 2 + 2 Punkte)

[erster Lösungsversuch: Wenn er richtig ist diesen Satz löschen, ansonsten bitte verbessern]

a)

L = h(D₂ ∩ {(}*{)}*{[}*{]}*)
wobei h:{(,),[,])* -->
h(()=aa
h())=d
h([)=b
h(])=cccc
Kritik an Lösungsversuch: Dieses h erlaubt es ()[] auf aadbcccc abzubilden, das entspricht aber nicht L

Verbesserung: L = h(D₂ ∩ {(}*{[}*{]}*{)}*)

b)

G_1 = <{S,A}, {a,b,c,d}, {S -> aaAd | ε, A -> bAcccc | ε},S>

G_1 ist falsch

Verbesserungsvorschlag:

G = <{S, A}, {a, b, c, d}, {S -> a²Sd | A, A -> bAcccc | ε}, S>

oben wäre es nicht möglich mehrere a's und d's zu haben, da S direkt zu A geht

c)

Ja, weil L eine kontextfreie Sprache ist und damit eine Teimenge von P. Und da P entweder eine Teilmenge oder gleich der Menge von NP ist und diese von nicht-deterministischen Turingmaschinen (NTM) entscheidbar sind, ist auch L von einer NTM entscheidbar.

Aufgabe 3 (5 + 3 Punkte)

[erster Lösungsversuch: Wenn er richtig ist diesen Satz löschen, ansonsten bitte verbessern]

a)

Der Satz von Rice besagt, dass eine Eigenschaft entscheidbar ist wenn sie entweder die Eigenschaft ist die Leersprache zu sein oder eine Eigenschaft ist die auf alle rekursiv aufzählbaren Sprachen zutrifft. Das heißt wenn man eine rekursiv aufzählbare Sprache findet auf die die Eigenschaft zutrifft und eine auf die es nicht zutrifft, dann ist diese Eigenschaft nicht entscheidbar.
L₁={1ⁿ | n ≥ 0}
L₂={1ⁿ | n ist Prim}

b)

	regulär	kontextfrei	kontextsensitiv	rekursiv	rekursiv aufzählbar
L1	Ja	Ja	Ja	Ja	Ja
L2	Nein	Nein	Ist ein ungeklärtes Problem	Ist ein ungeklärtes Problem	Ja

Aufgabe 4 (6 Punkte)

[erster Lösungsversuch: Wenn er richtig ist diesen Satz löschen, ansonsten bitte verbessern]

a)

Richtig, L_u ist rekursiv aufzählbar und somit auch A und A'. Wenn A und A' rekursiv aufzählbar sind dann sind sowohl A als auch A' sogar rekursiv.

b)

Wahr, wenn das Komplement von B endlich ist, ist B auch endlich (Abgeschlossenheit bezüglich Komplement). Wenn dann A in polynomieller Zeit auf B reduziert werden kann, dann ist A auch endlich, was eine Teilmenge von P ist.

c)

Wahr, wenn bewiesen wäre, das NP ≠ co-NP dann würde das bedeuten, dass es keine Polynomialzeitreduktion von NP auf co-NP/umgekehrt gäbe. Washalb dann auch gelten müsste P ≠ NP.

Aufgabe 5 (7 Punkte)

[erster Lösungsversuch: Wenn er richtig ist diesen Satz löschen, ansonsten bitte verbessern]

Signatur: <PS,KS,FS>

• PS:

 Studierende(x) ... x ist eine Studierende
 Prüfung(x) ... x ist eine Prüfung

• FS:

 besteht(x,y) ... x besteht y

• KS:

 Devi
 Analysis_2

(1)

∀x(Prüfung(x) ⊃ besteht(Studierende(Devi),x))

[Korretkurvorschlag]

Falsch mMn. das würde ja ausdrücken das Devi alle Prüfungen besteht.

∀x((Prüfung(x) ∧ x != Analysis_2) ⊃ besteht(Studierende(Devi),x))

(2)

∃x(Prüfung(x) ∧ ∃y∀z(y=z ∧ besteht(Studierende(y),x))

Aufgabe 6 (7 Punkte)

[erster Lösungsversuch: Wenn er richtig ist diesen Satz löschen, ansonsten bitte verbessern]

• Modell:

 D = ℕ
 Φ(P)(a,b) = true
 --> alles andere ist irrelevant
 --> Formel evaluiert zu true weil der rechte Teil der Disjunktion eine Implikation ist und dort der rechte Teil der Implikation wahr ist.

• Gegenbespiel:

 D = ℕ
 Φ(P) = '<'
 ξ(y) = '3'
 --> aus diesen beiden folgt dass P(x,y) wahr wird & das ∀yP(y,x) falsch wird
 Φ(Q) = '>'
 Φ(f) = 'Identitätsfunktion'
 --> daraus folgt dass ∀zQ(a, f(z)) falsch wird
 Φ(a) = '1'
 ξ(z) = '3'
 --> daraus folgt dass Q(z, a) wahr wird
 --> Beide Seiten der Disjuktion sind falsch weil die Implikationen falsch sind.

• freie Variablen: y, z
• gebundene Variablen: x, y, z

Aufgabe 8 (8 Punkte)

[erster Lösungsversuch: Wenn er richtig ist diesen Satz löschen, ansonsten bitte verbessern]

• Wahr:

 Partiell korrekt weil:
   Um nicht partiell korrekt zu sein, müsste es nicht korrekt sein. Um das zu erlangen müsste y < x und y ≥ 2x gelten was unmöglich ist.
 Nicht total korrekt weil:
   Bsp. x = -3 und y = -7, y wird immer mehr negativ aber die Schleife bricht nie ab

[Korrekturvorschlag]

• Falsch:

 x=-3, y=-5; Dann gilt -5 < -3 und -5 ≥ -6

• Wahr:

 Partiell korrekt weil:
   Damit die Schleife nicht eintritt muss gelten ¬R ∧ P, das heißt wenn die Schleife abbricht muss P gelten
 Nicht total korrekt weil:
   Wir wissen nicht was in α passiert, es kann sein dass die Schleife nie abbricht.