Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Automaten Äquivalenz

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Automaten Äquivalenz

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

syn_c
unregistriert

Automaten Äquivalenz

Zitatantwort auf diesen Beitrag erstellen

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.

syn_c hat dieses Bild (verkleinerte Version) angehängt:

05.11.2011 22:15

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Karlito: 07.11.2011 00:09.

06.11.2011 21:45

Nehmen Sie Karlito in Ihre Freundesliste auf

syn_c
unregistriert

thank you, habs verstanden.

21.11.2011 21:56

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automaten Äquivalenz