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

Aufgabe 1 (2 + 6 Punkte)

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

a) G = <{S}, {a,b}, {S -> abS | abSa | ab}, S>
b) L = {(ab)ⁿa^k | n > k, k ≥ 0}

  1. Wähle ein Wort: (ab)m+1am --> |w| = 2(m+1)+m > m
  2. Weil |xy| ≤ m kann xy nur aus Symbolen ab bestehen
  3. Wähle i = 0 --> (ab)m+1-|y|am
     Weil |y|>0 gilt, gilt sicher nicht mehr n>k --> Wort nicht in Sprache
     --> nicht regulär

Aufgabe 2 (2 + 2 + 2 + 2 Punkte)

a) L₁ = {a^2kb^4kc^3l | k, l ≥ 0}

  G = <{S, X, Y}, {a, b, c}, P, S>
  P:
    S -> XY | X | Y | ε
    X -> a2Xb4 | a2b4
    Y -> c3Y | c3

b)

• Monoton: Ja, weil |x| <= |y| für alle Produktionen gilt. Der Fall S -> ε wird ausgenommen, da S auf keiner rechten Seite der Produktion vorkommt.
• Kontextfrei: Ja, weil links nur Nonterminalsymbole und rechts Terminal- bzw. Nonterminalsymbole vorkommen.
• Regulär: Nein. Die Produktionsregeln einer regulären Grammatik lauten folgendermaßen: A -> aB oder A -> a. Also wäre beispielsweise S -> XY keine gültige Produktionsregel für reguläre Grammatiken.

c) L₁ ∩ L₂ = {a^2kb^4kc^3l| k,l ≥ 0}

d) Ja, weil sie von einer kontextfreien Grammatik erzeugt werden kann.

Aufgabe 3 (5 +3 Punkte)

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

a) Satz von Rice besagt, ein Problem ist Entscheidbar, wenn es eine Eigenschaft ist die auf alle rekursiv aufzählbaren Sprachen zutrifft oder die Eigenschaft ist die Leersprache zu sein. Daher wenn wir eine rekursiv aufzählbare Sprache angeben können die die Eigenschaft hat und eine die sie nicht hat, dann ist die Eigenschaft/das Problem nicht entscheidbar:
L₁ = {ϵ, 0ⁿ | n ≥ 0}, L₁⁺ = L₁^*
L₂ = {0ⁿ | n ≥ 0}, L₂⁺ ≠ L₂^*

b) Ja, beide sind von einer deterministischen Turingmaschine in polynomieller Zeit entscheidbar. Jedes Wort kann darauf geprüft werden nur aus 0 und bei L₁ dem Leerwort zu bestehen.

Aufgabe 4 (6 Punkte)

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

a) Falsch, es kann auch zufällig (Anmerkung: Nicht Zufall, sondern weil B eine Teilmenge von A ist) so sein dass die Sprache nicht regulär war. Bsp. A={0,1}* und B={0ⁿ 1ⁿ | n>= 0}
b) Wahr, jedes NP-Problem kann auf jedes NP-vollständige Problem (in dem Fall SAT) reduziert werden. Das bedeutet, alle NP-Probleme sind mindestens so schwer wie NP-vollständige Probleme.
c) Falsch, z.B. eine Sprache über dem Alphabet {0,1}* kann gebildet werden, dann wäre eine Teilmenge davon das Halteproblem und dieses kann nicht von einer NTM in polynomieller Zeit entschieden werden.

Aufgabe 5 (7 Punkte)

Lösungsvorschlag 1

Signatur: <PS, KS, FS>

• PS:

arbeitetAnTU(x) ... x arbeitet an TU
arbeitetAnETH(x) ... x arbeitet an ETH
kennt(x,y) ... x kennt y

• FS:

Studierender(x) ... x ist Studierender
Forscherin(x) ... x ist Forscherin

• KS: keine

(1) Kein Studierender kennt alle Forscherinnen, die an der TU Wien arbeiten.

   ¬∃x∀y((Studierender(x) ∧ Forscherin(y)) ⊃ arbeitetAnTU(y) ∧ kennt(x,y))

Anmerkung zu diesem Lösungsvorschlag: Diese Formel besagt meiner Meinung nach, dass alle Forscherinnen an der TU arbeiten und kein Studierender alle diese Forscherinnen kennt, und ist demnach nicht genau die gemeinte Aussage. Verbesserung:

   ¬∃x∀y((Studierender(x) ∧ Forscherin(y) ∧ arbeitetAnTU(y)) ⊃ kennt(x,y))

(2) Mindestens zwei Forscherinnen arbeiten sowohl an der TU Wien als auch an der ETH Zürich, aber kennen keinen Studierenden.

   ∃x∃y(Forscherin(x) ∧ Forscherin(y) ∧ x ≠ y ∧ arbeitetAnTU(x) ∧ arbeitetAnTU(y) ∧ arbeitetAnETH(x) ∧ arbeitetAnETH(y) ∧ ¬∃z(Studierender(z) ∧ kennt(x,z) ∧ kennt(y,z)))

Anmerkung zu diesem Lösungsvorschlag: Der Letze Teil dieser Formel besagt meiner Meinung nach, dass es keinen Studierenden z gibt, den x Kennt und y Kennt. Diese Formulierung erlaubt allerdings, dass die Forscherinnen unterschiedliche andere Studierende kennen, also auch hier wieder nicht das was gefragt war. Verbesserung:

    ∃x∃y(Forscherin(x) ∧ Forscherin(y) ∧ x ≠ y ∧ arbeitetAnTU(x) ∧ arbeitetAnTU(y) ∧ arbeitetAnETH(x) ∧ arbeitetAnETH(y) ∧ ∀z(Studierender(z) ⊃ ¬kennt(x,z) ∧ ¬kennt(y,z)))

Lösungsvorschlag 2

Signatur: <PS, KS, FS>

PS:
    StudentIn(x) ..... x ist StudentIn
    ForscherIn(x) .... x ist ForscherIn
    kennt(x, y) ...... x kennt y bzw. y kennt x
    arbeitet(x, y) ... x arbeitet an Universität y
KS:
    t ... TU Wien
    e ... ETH Zürich
FS:
    keine

(1)

∀s[StudentIn(s) ⊃ ¬(∀f[ForscherIn(f) ∧ kennt(s, f) ∧ arbeitet(f, t)])]

(2)

∃f∃o[(Forscher[f] ∧ Forscher[o] ∧ f ≠ o) ⊃                                  // Mindestens zwei Forscherinnen
     (arbeitet[f, t] ∧ arbeitet[f, e] ∧ arbeitet[o, t] ∧arbeitet[o, e] ∧    // arbeiten sowohl an der TU Wien als auch an der ETH Zürich,
      ∀s[¬kennt(f, s) ∧ ¬kennt(o, s)])]                                     // aber kennen keinen Studierenden

Aufgabe 6 (7 Punkte)

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

∀z[(R(z, h(z, d)) ∧ Q(z, y)) ⊃ ∃y(Q(h(y, z), x) ⊃ R(y, x))].

• Modell:
  

 D = ℕ 
 Φ(R)(a,b) = true 
 --> Alles andere ist irrelevant die Funktion evaluiert zu true wegen den Implikationen. 

• Gegenbeispiel:
  

 D = ℕ
 Φ(h) = '+'
 Φ(Q)(a,b) = true
 Φ(R) = '<'
 Φ(d) = 2
 ξ(x) = 0
 --> Alles andere ist irrelevant. Durch Φ(h), Φ(Q)(a,b), Φ(R) und Φ(d) wird der linke Teil der Implikation wahr und da x = 0 ist wird der rechte falsch. Damit wird die ganze Formel falsch.

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

Aufgabe 8 (8 Punkte)

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

• Falsch: Wähle y = -6 und x = -4, dann kommt man nie in die while Schleife und y ist am Ende nicht größer als 0.
• Richtig: Die Implikation kann auch ausgedrückt werden als ¬P∨Q. Das darf nicht erfüllt sein damit die Schleife abbricht das heißt P∧¬Q muss gelten --> Q ist immer negativ am Ende. --> partiell korrekt. Aber wir wissen nicht was in α passiert, das bedeutet die Formel kann auch nie falsch werden, deshalb gilt nicht totale Korrektheit.

Verbesserungsvorschlag:

1) ist Richtig, weil es gibt Belegungen, welche zu einem richitgen Ergebniss führen. y = -3, x = 1 => Partiell. Aber nicht total, weil y=-6, x=-4

Anmerkung zum Verbesserungsvorschlag:

Bei partieller Korrektheit gilt: Für JEDE Belegung wo die Vorbedingung passt und das Programm terminiert muss die Nachbedingung erfüllt sein. Also ist 1) weder partiell noch total korrekt (also Antwort Falsch hat eh gepasst), weil es zum Beispiel eben den Fall x=-4 und y=-6 gibt.