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?