Rouven: Teilmengenkonstruktion bei Automaten

Beitrag lesen

Hi,

ich form den gerade mal auf 3 um:

oder tabellarisch:

a       b
z0
z1
z2

Also, was ist das Problem an diesem Automaten? Du kannst spätestens nach dem Aufmalen feststellen, dass er bei Zustand 2 nicht deterministisch entscheidet wie er auf ein a reagiert: Er könnte entweder in s2 oder in s3 landen. Das kann natürlich deterministisch nicht entschieden werden. Die Lösung sieht nun so aus: Konstruiere alle Teilmengen der Zustände (d.h. alle Möglichkeiten die Zustände zu kombinieren) und nehme die Abbildungen dann vor. Anschließend mache aus jeder dieser Teilmengen einen Zustand (auf Deutsch: Mach im Diagramm einen Kreis drum):
Zustände sind { z0, z1, z2 }
Alle Teilmengen = neue Zustände:
{}
{ z0 }
{ z1 }
{ z2 }
{ z0, z1 }
{ z0, z2 }
{ z1, z2 }
{ z0, z1, z2 }
=2^3=8 Zustände...

Nun musst du die Originalübergangsfunktion "aufblähen" und in das neue Modell übersetzen, frei nach dem Motto wo immer der Zustand auf den das Original gezeigt hat drin ist, da muss ich jetzt auch wieder hinkommen (geht also ein Zustand z0 in z0 oder z1, dann geht er jetzt nach { z0,z1 } - Ab da muss man aufpassen, denn der Zustand { z0,z1 } zeigt nun auf alles, das vorher von z0 oder von z1 erreichbar war... ):
{} + a/b = {}
--
{ z0 } + a = { z0 }
{ z0 } + b = { z1 }
--
{ z1 } + a = { z0 }
{ z1 } + b = { z0 }
--
{ z2 } + a = { z1, z2 }
{ z2 } + b = { z1 }
--
{ z0, z1 } + a = { z0 }
{ z0, z1 } + b = { z0, z1 }
--
{ z0, z2 } + a = { z0, z1, z2 }
{ z0, z2 } + b = { z1 }
--
{ z1, z2 } + a = { z0, z1, z2 }
{ z1, z2 } + b = { z0, z1 }
--
{ z0, z1, z2 } + a = { z0, z1, z2 }
{ z0, z1, z2 } + b = { z0, z1 }

--> Nochmal, wichtig:
Am Beispiel von dem einen (!!) Zustand "{ z1, z2, z3 }" (denn der heißt jetzt so, diese Menge bildet einen Zustand) kann man sehen, man kommt beim Zeichen a dort hin wo man mit einem a von z1, z2 und z3 hingekommen ist, also zu {z1}+{z1}+{z2, z3}={ z1, z2, z3 }

Ich hoffe das ist jetzt richtig gewesen, sonst korrigier mich bitte jemand...

MfG
Rouven

--

-------------------
ss:) zu:) ls:& fo:) de:< va:{ ch:? sh:) n4:( rl:? br:$ js:| ie:) fl:(

MfG
Rouven

--

-------------------
ss:) zu:) ls:& fo:) de:< va:{ ch:? sh:) n4:( rl:? br:$ js:| ie:) fl:(