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

Aus VoWi
Zur Navigation springen Zur Suche springen

Aufgabe 1 (6 + 2 Punkte)[Bearbeiten | Quelltext bearbeiten]

[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)[Bearbeiten | Quelltext bearbeiten]

a)[Bearbeiten | Quelltext bearbeiten]

L = { a2n b4n c21i | n, i ≥ 0}

21i da kgV(7,3) = 21

b)[Bearbeiten | Quelltext bearbeiten]

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

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

c)[Bearbeiten | Quelltext bearbeiten]

      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)[Bearbeiten | Quelltext bearbeiten]

[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.

  • L1={1n0m | n,m ≥ 0} -> {1n | n≥0} -> rekursiv aufzählbar/regulär
  • L2={1n0m | n,m ≥ 0, n ist prim} -> {1n | 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)[Bearbeiten | Quelltext bearbeiten]

[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)[Bearbeiten | Quelltext bearbeiten]

[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)[Bearbeiten | Quelltext bearbeiten]

[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)[Bearbeiten | Quelltext bearbeiten]

[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)[Bearbeiten | Quelltext bearbeiten]

[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.