Gedächtnisprotokoll FGI209-2

Zum zweiten Versuch der FGI2-Klausur wurde in PhilA geschrieben, Aufsichten hatten Herr Valk und Herr Köhler. Insgesamt waren 181Punkte zu erreichen, der Schwierigkeitsgrad war ähnlich hoch wie zur ersten Klausur.

Aufgabe 1

• 1) Gegen waren zwei Transitionssysteme mit Sync = *leereMenge*. Geben sie das synchrone TS an.
• 2) Geben sie L(TS_1) und L(TS_2) an, bestimmen sie auch L(TS_3) = L(TS_1) \cap L(TS_2)

• 3) Formen sie TS_3 so um, dass es den Schnitt akzeptiert.
• 4) Geben sie die Synchronisationsmenge an.

Aufgabe 6

Zwei BPA-Terme waren gegeben.

• 1) Zeichnen sie die Prozessgraphen.
• 2) Kennzeichnen sie die bisimilaren Knoten.
• 3) Bestimmen sie die Normalformen mit den Regeln R1-R5.
• 4) Sind die Terme bisimilar?

Aufgabe 7

Hier kam eine Aufgabe zum rekursiven Ableiten dran.

• 1) Zeichnen sie den Prozessgraphen <X|E> mit {X=Ya+c, Y=Xc}.
• 2) Leiten sie <X|E> mit für die Aktion a ab.
• 3) Wann ist eine Spezifikation geschlossen?
• 4) Ist diese Spezifikation geschlossen?

Aufgabe 8

20 Punkte zu LTL und CTL

• 1) Gegeben war eine Kripkestruktur. Geben sie alle PLätze an wo die Formel gilt.
• 2) Wo liegen die Syntaktischen Unterschiede zwischen CTL und LTL?
• 3) Geben sie je eine Formel an die für CTL oder LTL nicht korrekt ist.
• 4) Geben sie Vor- und Nachteile von LTL- und CTL-Formeln an.
• 5) ...
• ...

Aufgabe 9

Man musste die logischen, nicht die vektoriellen, Zeitstempel eintragen.

Aufgabe 10

• 1) Wie unterscheiden sich der Ausfallalgorithmus von dem des byzantinischen Konsenses?
• 2) Was ist Nachrichtenkomplexität?
• 3) Geben Sie die Nachrichtenkomplexität des Ausfallalgorithmuses an.
• 4) Warum ist der erste Algorithmus aus der Vorlesung exponentiell?
• 5) Warum ist der zweite Algorithmus aus der Vorlesung polinomiell?