TU Wien:Theoretische Informatik und Logik VU (Fermüller)/Prüfung 2022-01-28 Lösung

Aufgabe 1 (6 + 2 Punkte)

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

a)

      1. Wähle Wort: w = a2022+mbm

      2. Beim Pumping Lemma wird das Wort w in x, y und z aufgeteilt, sodass |xy| ≤ m und |y| > 0 gilt. Daraus folgt also, dass xy nur aus a's bestehen kann, woraus man trivialerweise schließen kann, dass y auch aus a's bestehen muss.

      3. Versuchen wir nun w = xyiz = a2022+m+ibm aufzupumpen, merken wir, dass dieses Wort nicht mehr in der Sprache ist, da die Bedingung n-k=2022 nicht mehr eingehalten werden kann! Um einen Widerspruch zu zeigen, nehmen wir i = 2, wodurch wir xyyz erhalten. Das Wort xyyz ist nicht Element der Sprache, da die Bedingung n-k=2022 hier nicht erfüllt werden kann.

b) Ist entscheidbar weil es eine kontextfreie sprache ist und somit auch rekursiv, daher ist das komplement auch rekursiv/entscheidbar

Wenn L kontextfrei ist, dann ist L entscheidbar. Das heißt wir können für alle Wörter entscheiden ob sie Teil von L sind oder nicht.

Gefragt ist jedoch ob das Komplement von L entscheidbar ist. Das ist aber das selbe wie die Frage ob "Ist ein Wort *nicht* Teil von L" entscheidbar ist. Weil das Komplement einer Sprache sind ja alle Wörter die nicht Teil davon sind.

Kurzgefasst: "Ist ein Wort Teil von L-Komplement" <=> "Ist ein Wort nicht Teil von L", folglich ist L-Komplement auch entscheidbar.

Alternative:

b) ist nicht entscheidbar (siehe S. 169 - Entscheidungsprobleme für kontextfreie Sprachen)

Aufgabe 2 (2 + 2 + 4 Punkte)

a)

L = { a²ⁿ b⁴ⁿ c²¹ⁱ | n, i ≥ 0}

21i da kgV(7,3) = 21

b)

G = <{S,T,C}, {a,b,c}, P, S>

  P = S -> AC
      A -> ϵ | a2Ab4
      C -> ϵ | c21C

c)

      L= h(D2 ∩ {[}*, {(}*, {)}*, {]}*)
      h:{(,),[,]} -> h(() = a2
                     h()) = b4
                     h([) = ϵ
                     h(]) = c21

Korrektur:

Da a und b beide hoch n sind müssen sie beide die selbe Klammerart haben, somit ist das R hier falsch richtig wäre

{(}*, {)}*, { [ }*, { ] }*

Aufgabe 3 (5 + 3 Punkte)

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

a) Satz von Rice besagt, dass ein Problem entscheidbar ist, wenn es die Eigenschaft hat die Leersprache oder rekursiv aufzählbar zu sein. Da reguläre Sprachen eine Teilmenge der rekursiv aufzählbaren Sprachen ist, kann mit zwei Sprachen die jeweils regulär/nicht rekursiv aufzählbar sind bewiesen werden, dass das Problem nicht entscheidbar ist.

• L₁={1ⁿ0^m | n,m ≥ 0} -> {1ⁿ | n≥0} -> rekursiv aufzählbar/regulär
• L₂={1ⁿ0^m | n,m ≥ 0, n ist prim} -> {1ⁿ | n≥0, n ist prim} -> rekursiv aufzählbar/nicht regulär
  

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]

[edit: Habe das erste korrigiert, bei den anderen bin ich mir nicht ganz sicher]

- Wahr. L ist eine Sprache über Σ und damit eine Teilmenge von Σ*. Dadurch ist L U Σ* = Σ*. Die Sprache Σ* ist regulär und in NP (sogar in P).
- Wahr. Wenn man A in polynomieller Laufzeit auf das NP-vollständige Problem SAT reduzieren kann - und umgekehrt - dann ist A auch NP-vollständig.
- Wahr. Wenn P=NP gilt, bedeutet das, dass alle Probleme, die in polynomialer Zeit gelöst werden können, auch von nicht-deterministischen Polynomialzeit-Algorithmen gelöst werden können und somit müsste NP = co-NP.

Anmerkung zu Antwort 2: Die Aussage A<=p SAT reicht bereits als Begründung. Also eher nicht wahr.

Anmerkung zur Anmerkung: Es gibt zwei Eigenschaften die erfüllt werden müssen, dass A NP Vollständig ist. A muss NP - Schwer sein und NP-Vollständig sein. Da du hier eine Reduktion von A auf SAT hast, weiß man, dass A MINDESTENS so schwer ist wie NP (A=NP) und da SAT auf A reduziert werden kann (und SAT NP-V ist) ist A somit NP-Schwer => A ist NP-V

Aufgabe 5 (7 Punkte)

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

Mutter(x) ... Mutter von x
Vater(x) ... Vater von x
istSchwester(x,y) ... x ist Schwester von y
istBruder(x,y) ... x, ist Bruder von y
kennt(x,y) ... x kennt y

(1): Die Mutter von Adas Vater hat genau eine Schwester, aber Adas Vater kennt diese nicht.

∃y∀x(¬(kennt(Vater(Ada),x)∧istSchwester(x,Mutter(Vater(Ada))))⊃(x = y))


Alternativer Lösungsvorschlag:

Signatur <{S,K},{a},{m,v}> mit folgender intendierter Bedeutung:

Prädikatensymbole: S(x,y) ... x ist die Schwester von y K(x,y) ... x kennt y

Konstantensymbole: a ... Ada

Funktionssymbole: m(x) ... Mutter von x v(x) ... Vater von x

∃x(S(x, m(v(a)) ∧ ¬K((v(a),x) ∧ ∀y(S(y,m(v(a))) ⊃(x = y)))

(2): Ada kennt keinen Bruder und keine Schwester ihrer Mutter.

¬∃x(kennt(Ada,x)∧(istSchwester(x,Mutter(Ada))∨istBruder(x,Mutter(Ada)))

Aufgabe 6 (7 Punkte)

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

∀x[(Q(x, y) ⊃ ∀zP (c, f (z))) ∨ (R(z, c) ⊃ ∀yQ(x, y))]

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

Modell: I = ⟨w, Φ_I , ξ_I ⟩
Φ_I(Q)(a,b) = f
Alle anderen spielen keine Rolle, da nur ein Teil der Disjunktion wahr werden muss und dort auch nur der linke Teil der Implikation falsch sein muss.

Gegenbeispiel: J = ⟨w, Φ_J , ξ_J ⟩
Φ_J(Q)= "≥" & ξ_J(x) = 0 --> ∀yQ(x, y) = f
Φ_J(R)(a,b)= t --> R(z,c) = t
Φ_J(P)(d,f)= f --> ∀zP(c, f(z)) = f
ξ_J(y) = 0 --> Q(x, y) = t
--> die gesamte Formel evaluiert zu false.

Aufgabe 7 (8 Punkte)

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

(1)	t: ∀x g(x) = x	Annahme / γ-Formel
(2)	f: ∃x[Q(g(x), x) ⊃ ∀yQ(y, y)]	Annahme / γ-Formel
(3)	f: Q(g(a), a) ⊃ ∀yQ(y, y)	von 2
(4)	t: Q(g(a), a)	von 3
(5)	f: ∀yQ(y, y)	von 3 / γ-Formel
(6)	f: Q(a, a)	von 5
(7)	t: g(a) = a	von 1
(8)	t: Q(a, a)	von 4 / S=: 7->4
	X Wiederspruch 8/6

[Korrekturversuch] [Das problem bei der oberen Variante ist im Schritt 5. Da true with "For all" soll in delta rule resultieren]

(1)	t: ∀x g(x) = x	Annahme / γ-Formel
(2)	f: ∃x[Q(g(x), x) ⊃ ∀yQ(y, y)]	Annahme / γ-Formel
(3)	f: Q(g(a), a) ⊃ ∀yQ(y, y)	von 2
(4)	t: Q(g(a), a)	von 3
(5)	f: ∀yQ(y, y)	von 3 / delta-Formel
(6)	f: Q(b, b)	von 5
(7)	t: g(b) = b	von 1
(8)	f: Q(g(b), b)	S=: 7->6
(9)	f: Q(g(b), b) ⊃ ∀yQ(y, y)	von 2
(10)	t: Q(g(b), b)	von 9
	X Wiederspruch 8/10

Aufgabe 8 (8 Punkte)

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

1) Die Aussage ist korrekt.

• Partiell Korrekt:
  

                  1. Fall y ≥ 2x --> {y ≥ x} ist true 

                  2. Fall y < 2x --> um nicht zumindest partiell korrekt zu sein müsste gelten 2x < 2y +x ≤ x was nicht sein kann --> partiell korrekt 

• Total Korrekt: z.B. y = -5, x = 2
  

                  1. Runde: y = -8 --> y < 2x 

                  2. Runde: y = -14 --> y < 2x etc. --> nicht total korrekt 

2) Die Aussage ist falsch. Es ist weder partiell noch total korrekt. Da α nicht bestimmt ist, kann es sein, dass P am Ende negativ ist.