Teoria śladów.

Cz. II

Dane są:

• Alfabet A, w którym każda litera oznacza akcję.
• Relacja niezależności I, oznaczająca które akcje są niezależne (przemienne, tzn. można je wykonać w dowolnej kolejności i nie zmienia to wyniku końcowego).
• Słowo w oznaczające przykładowe wykonanie sekwencji akcji.

Zadanie

Napisz program w dowolnym języku, który:

1. Wyznacza relację niezależności I
2. Wyznacza ślad [w] względem relacji I
3. Wyznacza postać normalną Foaty FNF([w]) śladu [w]
4. Wyznacza graf zależności dla słowa w
5. Wyznacza postać normalną Foaty na podstawie grafu

Do zadania należy dostarczyć sprawozdanie, które będzie zawierać:

1. Opis programu z komentarzami
2. Wyniki działania dla przykładowych danych

Sprawozdanie i kod programu proszę przysłać na adres: funika@agh.edu.pl

Uwagi:

• Proszę wykorzystać algorytm ze str. 10 rozdziału Partial commutation and traces (pochodzi z Handbook of Formal Languages, Springer, 1997.
• Do rysowania grafu można wykorzystać Graphviz i format DOT. Wersja online: Webgraphviz.

Przykład

Dla danych:

(a) x := x + y

(b) y := y + 2z

(c) x := 3x + z

(d) z := y - z.

A = {a, b, c, d}

I = {(a, d), (d, a), (b, c), (c, b)}

w = baadcb

Wyniki:

1. D = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, d), (c, a), (c, c), (c, d), (d, b), (d, c), (d, d)}
2. FNF([w]) = (b)(ad)(a)(bc)
3. Graf w formacie dot:

digraph g{
 1 -> 2
 2 -> 3
 1 -> 4
 3 -> 5
 4 -> 5
 3 -> 6
 4 -> 6
 1[label=b] 
 2[label=a]
 3[label=a]
 4[label=d] 
 5[label=b]
 6[label=c]
}

Dane testowe 2:

• A = {a, b, c, d, e, f}
• I = {(a, d), (d, a), (b, e), (e, b), (c, d), (d, c), (c, f), (f, c)}
• w = acdcfbbe

---