Informatiker Board | Druckvorschau: Automaten Äquivalenz

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Automaten Äquivalenz (http://www.informatikerboard.de/board/thread.php?threadid=1067)

Geschrieben von syn_c am 05.11.2011 um 22:15:

Automaten Äquivalenz

Hallo, leider habe ich eine Vorlesung verpasst und nun verstehe ich eine Aufgabe nicht.
Kann mir vielleicht einer einen kleinen Anschubser geben?

Ich hab das Problem das ich nicht weiß wie ich die Mengen für 1. a.) berechne und aus den Äquivalenten, Äquivalenzklassen bilde?

Vielen Dank für jede Hilfe.

Geschrieben von Karlito am 06.11.2011 um 21:45:

Hi,

1. Bilde Eine Menge mit 2 Teilmengen, wobei die eine Teilmenge die Zielzustände umfasst und die andere Teilmenge die restlichen Zustände.
2. Entnehme aus jeder Teilmenge diejenigen Zustände, die mit den gleichen Übergängen in die gleiche Teilmenge übergehen (z.B. Z2 und Z3 gehen mit den selben Übergängen in die Teilmenge der Endzustände über) und füge sie als neue Teilmenge hinzu.
3. Fahre mit der entstandenen Menge von Teilmengen bei 2. fort bis sich keine Änderung mehr ergibt.

Diejenigen Teilmengen von Zuständen die eine Mächtigkeit > 1 besitzen fassen die Äquivalenten Zustände zusammen.

Konkret auf die Aufgabe bezogen:
$[latex] \sim_0 & = & \{\{Z_0, Z_1, Z_2, Z_3, Z_6\},\{Z_4, Z_5\}\} \sim_1 & = & \{\{Z_0, Z_1, Z_6\},\{ Z_2, Z_3\},\{Z_4, Z_5\}\} \sim_2 & = & \{\{Z_0, Z_6\},\{ Z_1\},\{ Z_2, Z_3\},\{Z_4, Z_5\}\} \sim_3 & = & \{\{Z_0\},\{Z_6\},\{ Z_1\},\{ Z_2, Z_3\},\{Z_4, Z_5\}\} \sim_4 & = & \sim_3 &\Rightarrow & \mbox{Die Zustände} \{Z_2, Z_3\} \mbox{und} \{Z_4, Z_5\} \mbox{ sind äquivalent} [/latex]$

Ich hoffe das hilft und ich hoffe ich habe mich nicht irgendwo vertan. Wenn es noch Unklarheiten gibt, dann bitte noch mal konkret nachfragen. Is glaube ni so leicht beim ersten mal...

VG,

Karlito