Bearbeiten von „Gedächtnisprotokoll FGI210-1“

Aufgabe 1


TS1 und TS2 gegeben

1. L(TS1) und L(TS2) angeben

2. Produktautomaten TS3 konstruieren

3. L(TS3) "berechnen"

4. Gilt L(TS3) = L(TS1) geschnitten L(TS2)? Falls ja, gilt dies sogar allgemein?

5.

Aufgabe X


Algorithmus so ungefähr gegeben:

 f(n)
 {
 v := 0
   for i=0 to n
   {
      v:=v+i;
   }
 return v;
 }

1. Welchen Ausdruck berechnet der Algorithmus für n>0?

2. und 3. Zeit- und Platzkomplexität uniform und logarithmisch


Aufgabe X


Kripke-Struktur gegeben.

Per CTL-Algorithmus soll geprüft werden, ob EGa gilt.


1. Markiere alle Zustände (+ dazugehörende Kanten), in denen a gilt

2. Markiere alle SZK und kennzeichne die nicht trivialen.

3. Falls EGa gilt, gib einen entsprechenden Pfad in klein-omega-Schreibweise an. Wie berechnet der Algorithmus diesen Pfad?


Außerdem gabs noch Aufgaben: Petrinetze, Vektorielle Zeitstempel, BPA Prozessgraphen und Bisimilarität, Paralleloperator und Prozessgraph