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

Aufgabe 1 (2 + 6 Punkte)

[Siehe für a Aufgabe 2.1 a) und für b Aufgabe 1.5 a)

a)

G = <{S}, {a,b,c}, {S -> aSa | bSb | cSc | ϵ}

b)

1) Wort auswählen: a^mbba^m --> |w| ≥ m
2) |xy| ≤ m, das heißt |xy| besteht nur aus Symbolen a
3) i wählen: i = 2
4) a^m+|y|bba^m
--> ww^r gilt nicht mehr weil |y|>0

Aufgabe 2 (6 + 2 Punkte)

a)

 L = h(D2 ∩ {([}*{)]}*)
 h: {(,),[,]}* -> {a,b,c}
 h(() = aa
 h([) = aa
 h()) = b
 h(]) = c

b)

Ja hier die Grammatik:

 G = ({S,X}, {a,b,c}, P, S)
 P:
   S -> X | ε
   X -> aaXb | aaXc | aab | aac

Aufgabe 3 (6 + 2 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 wenn sie auf alle rekurisv aufzählbaren Sprachen zutrifft. Das heißt wenn man eine rekurisv aufzählbare Sprache findet auf die diese Eigenschaft zutriffe und eine auf die es nicht zutrifft, dann ist die Eigenschaft nicht entscheidbar.
L₁ = {0ⁿ|n>1}
L₂ = {ϵ, 0ⁿ|n>1}

b)

L_1' = Σ* \ {0ⁿ|n>1} --> enthält ϵ
L_2' = Σ* \ {ϵ, 0ⁿ|n>1} --> enthält nicht ϵ

Aufgabe 4 (6 Punkte)

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

a)

Nein, nicht alle entscheidbaren Sprachen liegen in P und auch nicht alle Sprachen deren Komplement entscheidbar ist müssen in P liegen.

b)

Nein, es gibt auch Probleme die nicht in NP liegen aber in exponentieller Zeit gelöst werden können (Halteproblem)

c)

Nein es kann auch zufällig so sein, dass die Sprache nicht regulär ist. Bsp: A = {1ⁿ 0ⁿ | n ≥ 0}, B = A ∩ {1}* = {1ⁿ | n ≥ 0}

Aufgabe 5 (7 Punkte)

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

Signatur <PS, KS, FS>

• PS: spricht, sieht
• FS: Papagei, Mensch
• KS: Egmont

Papagei(x) ... x ist Papagei
Mensch(x) ... x ist Mensch
spricht(x,y) ... x spricht mit y
sieht(x,y) ... x sieht y

(1) ∀x∀y((Papagei(x) ∧ Mensch(y)) ⊃ (sieht(x,y) ⊃ spricht(x,y)))

Korrekturversuch: ∀x∀y((Papagei(x) ∧ Mensch(y) ∧ sieht(x,y)) ⊃ (spricht(x,y))

Papagei und Mensch impliziert nicht, dass der Papagei den Menschen auch sieht
(2) Papagei(Egmont) ∧ ¬ ∃x∃y∃z[ Mensch(x) ∧ Mensch(y) ∧ Mensch(z) ∧ spricht(Egmont,x) ∧ spricht(Egmont,y)∧ spricht(Egmont,z) ∧ ¬(x=y) ∧ ¬(x=z) ∧ ¬(z=y) ]

Andere Lösung lt. Folie 384 (höchstens zwei) (bin mir nicht ganz sicher ob das richtig ist -> bitte löschen wenn falsch):

(2) Papagei(Egmont) ∧ ∃x∃y∃z[ Mensch(x) ∧ Mensch(y) ∧ Mensch(z) ∧ spricht(Egmont,x) ∧ spricht(Egmont,y)∧ spricht(Egmont,z) ∧ ((z = x) ∨ (z=y)) ]

Verbesserungsvorschlag zu 2:

Ich denke es gehört eher so: Papagei(Egmont) ∧ ∃x∃y∀z[ (Mensch(x) ∧ Mensch(y) ∧ Mensch(z) ∧ spricht(Egmont,x) ∧ spricht(Egmont,y)∧ spricht(Egmont,z)) ⊃ ((z = x) ∨ (z=y)) ]

Aufgabe 6 (7 Punkte)

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

∀z[(R(z, z) ∧ ¬R(h(d, z), y)) ⊃ ∀y¬R(h(y, z), x)]

• Modell:

 D = ℕ
 Φ(R)(a,b) = f
 --> alles andere ist irrelevant
 --> der rechte Teil der Implikation ist wahr somit ist die Formel wahr.

• Gegenbeispiel:

 D = ℕ
 Φ(R)='≤'
 Φ(h)(a,b)='b'
 Φ(y) = 10 --> aus den ersten 3 folgt das der linke Teil der Implikation wahr wird
 Φ(x) = 0 --> aus allen folgt das der rechte Teil der Implikation falsch wird
 --> Der Wert für die Konstante d ist egal.
 --> Die Formel evaluiert zu false

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

Aufgabe 7 (8 Punkte)

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

(1)	f: ∃x[(P(x, f(x)) ∧ ∀y y = f(y)) ⊃ ∀zP(z, z)]	Annahme / γ-Formel
(2)	f: (P(a, f(a)) ∧ ∀y y = f(y)) ⊃ ∀zP(z, z)	von 1
(3)	t: P(a, f(a)) ∧ ∀y y = f(y)	von 2
(4)	f: ∀zP(z, z)	von 2 / δ-Formel
(5)	t: P(a, f(a))	von 3
(6)	t: ∀y y = f(y)	von 3 / γ-Formel
(7)	f: P(b, b)	von 4
(8)	t: a = f(a)	von 6
(9)	t: P(a, a)	S=: 8->5
(10)	f: (P(b, f(b)) ∧ ∀y y = f(y)) ⊃ ∀zP(z, z)	von 1
(11)	t: P(b, f(b)) ∧ ∀y y = f(y)	von 10
(12)	f: ∀zP(z, z)	von 11 / δ-Formel
(13)	t: P(b, f(b))	von 11
(14)	t: ∀y y = f(y)	von 11 / γ-Formel
(15)	t: b = f(b)	von 14
(16)	t: P(b, b)	S=: 15->13
	X Wiederspruch 7/16

Aufgabe 8 (8 Punkte)

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

• Wahr:

 Partiell Korrekt, weil z > 2x gelten muss damit die Schleife abbricht und das auf jeden Fall größer ist als x-1
 Nicht Total Korrekt, weil für z<=0 bricht die Schleife nie ab.

• Falsch (?): Weil Q ⊃ R auch gelten kann, wenn man ¬Q und ¬R verwendet und damit wäre Q am Ende ¬Q

[Korrekturvorschlag]

a)

Falsch: weder Total noch partiell korrekt:

Gegenbeispiel: z=-2; x=-1

• Die Vorbedingung {z<5} ist korrekt da -2<5
• Die Schleifenbedingung z<2x ist falsch da z=2x -> die Schleife wird nie durchlaufen und davor schon beendet
• Nachbedingung: {z>x-1} gilt dann nicht da z=-2=-2=x-1

b)

Falsch: Gegenbeispiel wäre wenn Q = false und R = true: Die Vorbedingung ist erfüllt, aber es wird gar nicht in die while-Schleife hineingegangen. Die Nachbedingung ist aber dann falsch (Q müsste true sein)!