Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

minimaler Zustandsgraph
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> minimaler Zustandsgraph
 
Autor Nachricht
farnold
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 28.09.2008
Beiträge: 219

BeitragVerfasst am: 07 Jan 2010 - 17:17:03    Titel: minimaler Zustandsgraph

Hallo,

wir haben vor längerer Zeit mal eine Mehtode gehabt wie man ganz einfach in einem Zustandsgraph redundante Zustände finden konnte, leider kann ich mich nicht mehr genau an die Definition erinnern.
Bei dieser Mehtode ist man ohne Tabellen und Äquivalenzklassen ausgekommen.

Stimmt es, dass ein Zustande äquivalent zu einem anderen ist, wenn der eine Zustand dieselben ausgehenden Kanten (der Form "Eingabe/Ausgabe") hat wie der andere?
Oder muss zusätzlich der Folgezustand derselbe sein und die eingehenden Kanten auch?
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.07.2008
Beiträge: 3004
Wohnort: Gießen

BeitragVerfasst am: 07 Jan 2010 - 18:19:22    Titel:

http://theo.cs.uni-magdeburg.de/lehre04s/dc/dc04_s_kap3.pdf hat folgendes geschrieben:
Der Reduktionsalgorithmus besteht aus den folgenden Schritten:
1. Erstelle eine Liste aller Paare (z, z') von Zuständen z ∈ Z und z' ∈ Z.
2. Streiche ein Paar (z, z') falls entweder z ∈ F und z' !∈ F oder z !∈ F und z' ∈ F gilt.
3. Führe die folgende Aktion solange aus, bis keine Markierungen mehr in der Liste möglich sind: Falls für ein Paar (z, z') und ein a ∈ X das Paar (δ(z, a), δ(z', a)) nicht in der Liste ist, so streiche (z, z').
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> minimaler Zustandsgraph
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum