Teilmengenkonstruktion bei Automaten

[Horst]

Hallo zusammen,

hoffe es kann mir jemand helfen:
Wie funktioniert die Teilmengenkonstruktion bei Automaten?
Beispiel für einen Automaten:
(s0, a) = s1
(s0, b) = s2
(s1, a) = s1
(s1, b) = s1
(s2, a) = s2, s3
(s2, b) = s2

oder tabellarisch:
  | a       b
---------------
s0| s1      s2
s1| s1      s1
s2| s2,s3   s2

Man muß mittels der Teilmengenkonstruktion den deterministischen
Automaten finden.

Ich habe im Netz auch schon einiges gefunden, leider steht
fast überall: es ist so leicht... (z.B. http://520046051430-0001.bei.t-online.de/endliche_automaten.htm
leider verstehe ich es trotzdem nicht.

Mit Grüßen
der Horst

[Rouven]

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

[Horst]

Hi Rouven,

danke schon mal, werde es mir morgen mal in Ruhe anschauen.
Falls sich herausstellen sollte, dass mein Dozent anderer Meinung
ist, kann ich das ja ggf nochmal posten

Gruss
Horst