Hi,

kann mir jemand von Euch einen Tip geben, wo ich etwas zum Färbealgorithmus im Skript finde.

Bzw. was ist das für ein Algorithmus?


LG Frischling

das steht auf seite 82 im skript, 3.53

Bedeutet dass, dass man erst alle Kanten erstellen sol, also (Z0,Z1), (Z0,Z2)….. kann das Jemand etwas verständlicher audrücken als im Skript?
Was soll (P)hoch a ungleich (q)hoch b bedeuten???
Ich brauche wirklich hilfe!

gabs kein beispiel in der vorlesung?

wenn doch kann man sich das ja downloaden:
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS03/F2/index.html

zunächst erstellt man (wie es da auch steht ;) )
lauter knoten (Z0,Z1), …, jeder mit jedem einmal,
ergibt sowas schönes

{0,1} {0,2} ................... {1,2} ................... ................... ............... ........... {n-1,n}
dann halt alles schwarz, wie es bei INITIALISIERUNG steht,
alle paare, bei denen GENAU einer endzustand ist,
[diese knoten sind garantiert nicht äquivalent, leeres wort unterscheidet sie]

und dann geht man die knoten durch wie bei FÄRBEKONSTRUKTION beschrieben,

weiss anmalen
[erst mal annehmen, sie wären äquivalent],

für alle buchstaben a:
{(p)^a,(q)^a} herausfinden
(schauen in welchen knoten man mit jedem buchstaben kommt,
(p)^a = Zi <=> kante von p zu Zi mit inschrift a im automat),

ist (p)^a = (q)^a so führen die kanten zum gleichen zustand
im automaten, das ist dann uninteressant

* wenn zu einem schwarzen knoten:
knoten selber auch schwarz anmalen,
[wenn man mit einem buchstaben zu nichtäquivalenten zuständen kommt,
sind die zustände p und q selber auch nicht äquivalent]
alle knoten von denen färbealgorithmus-kanten zu {p,q} führen auch schwarz anmalen
[sind aus gleichem grund auch nicht äquivalent]
wenn man will kann man jetzt aus sauberkeitsgründen die färbealgorithmus-kanten noch entfernen,
fertig mit diesem knoten, nicht mehr weitere buchstaben betrachten

* wenn zu einem weissen knoten:
färbealgorithmus-kante von {p,q} zu diesem knoten malen
[falls dieser weisse knoten irgendwann mal schwarz wird,
muss ja {p,q} auch schwarz werden],


fertig,
alle weissen sind äquivalent, die schwarzen nicht

Also vom Knoten (1,2) folgere ich (1,a,2), (1,b,0), (2,a,1), (2,b,3) Und zu welchem Knoten führt das nun???

Also vom Knoten (1,2) folgere ich (1,a,2), (1,b,0), (2,a,1), (2,b,3) Und zu welchem Knoten führt das nun???

tja, ne schleife über alle buchstaben ist nun mal ne schleife über alle buchstaben

knoten(1,2)
für buchstabe a:

((1)^a,(2)^a) = (2,1)

für buchstabe b:

((1)^b,(2)^b) = (0,3)

wenn deine zahlen stimmen

und was ist wenn der eine Knoten z.b. für a Scharz und für b der selbe Knoten ist, also zu einem "noch" weissen Knoten führt?

wie schon geschrieben, sobald der knoten, den man bearbeit, schwarz ist,
ist das endgültig, und man kann zum nächsten übergehen,

und wie du obern ja richtig raus geschrieben hast kommt bei mir z.B. Knoten (2,1) raus, doch da es bei der Schreibweise so ist, dass die erste Zahl kleiner sein muss gilt dann:
(2,1)= (1,2).
Wenn dann kommt bei mir alles nicht äquivalentes raus. Ich kann mir nicht vorstellen dass es so sein sollte!

Und ist der Knoten (1,1) zugelassen????

und wie du obern ja richtig raus geschrieben hast kommt bei mir z.B. Knoten (2,1) raus, doch da es bei der Schreibweise so ist, dass die erste Zahl kleiner sein muss gilt dann:
(2,1)= (1,2).

richtig, hätte ich gleich so schreiben sollen,
richtig geschrieben heisst es ja auch
{2,1}= {1,2}
das sind mengen und keine tupel, eben weil reihenfolge irrelevant ist

Wenn dann kommt bei mir alles nicht äquivalentes raus. Ich kann mir nicht vorstellen dass es so sein sollte!

soso ;)

Und ist der Knoten (1,1) zugelassen????

wie auch schon geschrieben: nein
ist doch uninteressant ob zustand 1 und zustand 1 äquivalent sind

Soweit wie ich es aus den Folien gelesen habe wird die Kante vernachlässigt, wenn z.B. (1,d,4), (1,c,3), (2,d,4), (2,c,3)
folgt ja für Knoten (1,2) und das Symbol c:
(3,3)
und für d (4,4)
dann sollen wir dieses ergebnis einfach weglassen?
da es in unserer dreiecksliste nicht vorkommt! Also wird es weiss gefärbt?

Soweit wie ich es aus den Folien gelesen habe wird die Kante vernachlässigt, wenn z.B. (1,d,4), (1,c,3), (2,d,4), (2,c,3)
folgt ja für Knoten (1,2) und das Symbol c:
(3,3)
und für d (4,4)
dann sollen wir dieses ergebnis einfach weglassen?
da es in unserer dreiecksliste nicht vorkommt! Also wird es weiss gefärbt?

bevor man zu so einer situation kommt, hat man ja zu beginn
der bearbeitung eines knotens diesen schon weiss gefärbt,

und wenn nun bei einem buchstaben sowas wie (4,4) rauskommt,
dann ist das uninteressant, weil das nichts neues in hinblick
auf die nichtäquivalenz des knotens bringt,

man kann dann ruhig den weissen knoten nochmal weiss färben,
oder auch gar nichts tun und zum nächsten buchstaben übergehen

Danke. Nun habe auch ich es endlich geschnallt!
Slater du bist ein Genie!!! [img]http://www.fb18.de/gfx/7.gif[/img]
in welchem Semester bist du?

danke, danke,
4. semester halt

Hi,

nun melde ich mich mal wieder zu Wort. Eine Frage:

Wenn ich ((x)^a, (y)^a))={z,z} und ((x)^b, (y)^b))={d, d} bleibt doch (x, y) weiß, oder.

Also nach dem Färbealgorithmus müßten bei Aufgabe 6.2 zwei Zustände äquivalent sein.
Zu dem einen Zustand führt aber ein a und zu dem andern nicht!

e–a->x—b–>y—a—>e

Mach ich nun was falsch oder kann sowas wirklich dann trotzdem äquivalent sein?

LG Frischling

Hi,

nun melde ich mich mal wieder zu Wort. Eine Frage:

Wenn ich ((x)^a, (y)^a))={z,z} und ((x)^b, (y)^b))={d, d} bleibt doch (x, y) weiß, oder.

jo

Also nach dem Färbealgorithmus müßten bei Aufgabe 6.2 zwei Zustände äquivalent sein.
Zu dem einen Zustand führt aber ein a und zu dem andern nicht!

e–a->x—b–>y—a—>e

Mach ich nun was falsch oder kann sowas wirklich dann trotzdem äquivalent sein?

LG Frischling

weiss jetzt nicht so genau was du mit der e,x,y-schleife ausdrücken willst,

aber allgemein ist für die äquivalenz zweier zustände nur die
Leistung dieser zustände wichtig, also welche wörter man von
den zuständen aus noch akzeptieren kann (seite 77, 3.45),
nicht aber wie man zu den zuständen hinkommt,
also stört das nicht, das man zu dem einen erst ein a lesen muss,

Ok ich habe es glaube ich begriffen und auch dann richtig. Mit dieser e… -Schleife meinte ich das ganze ein bischen Umständlich:

Ich habe zwei Zustände, die jeweils mit dem gleichem Buchstaben in den gleichen Zustand führen => z.B. (z1 a z5) und (z2 a z5) ebenfalls auch (z1 b z6) und (z2 b z6).

Mein Problem war, das vom z5 betrachte einmal folgendes gilt (z5 a z1) aber es gilt nicht (z5 a z2).

Sowies aber scheint ist das irrelevant, da ich ja die Äquivalenz von z1 und z2 betrachte.

LG Frischling

PS: Die Zustände sind natürlich fiktiv und nicht aus der Aufgabe 6.2 (dort gibt es aber so einen Fall!).

ah, das ist dann ein etwas anderes problem,

aber richtigerweise auch irrelevant