| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
 Verfasst am: 20. Aug 2005 19:54 Titel: DFA aus NFA per Potenzmengenkonstruktion erstellen |
 |
|
Eigentlich ist mir das relativ klar.
Nur gibt es da einen Trick, bei dem man auf Angabe von Uebergaengen in unerreichbare Zustaende (vom Startzustand aus nicht erreichbar?!?) verzichten kann, den blicke ich nicht und er hat mir in der letzten Klausur den Kopf gekostet  (da das Erstellen deshalb ewig ging).
Das konkrete Beispiel - gegebener NFA sah so aus (da Zeichnung schlecht geht (der NFA war als Zeichung gegeben, schreibe ich die Zustandstabelle auf):
Delta_q0_____q1___q2_____q3
a___q0,q1_________q3_____q3
b___q0______q2__________q3
c___q0__________________ q3
(in der Klausur habe ich 25 min. gebraucht fuer das Riesenkonstrukt (ohne Anwendung des mysterioesen Tricks  )
Weiss jemand, wie das geht? Thx...  |
|
| Nach oben |
|
 |
|
|
Georg
Administrator
Anmeldungsdatum: 15.02.2005
Beiträge: 57
Wohnort: Aachen
|
| Verfasst am: 21. Aug 2005 11:26 Titel: |
|
|
Hi,
es wäre bestimmt hilfreich, wenn Du mal eben per Paint oder so die Zeichnung machen würdest, ich werde aus der Tabelle nämlich überhaupt nicht schlau |
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
| Verfasst am: 23. Aug 2005 10:18 Titel: |
|
|
Hat vielleicht einer 'ne Idee dazu?   Ich meine, schon auf die Lösung gekommen zu sein, bin mir aber nicht sicher, ob das stimmt. |
|
| Nach oben |
|
|
kurellajunior
Administrator
Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow
|
| Verfasst am: 23. Aug 2005 15:05 Titel: |
|
|
Dann zeig die Lösung hier, und wir prüfen sie gerne, oder geben weitere hinweise
_________________
 |
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
| Verfasst am: 23. Aug 2005 15:31 Titel: |
|
|
Ihr macht es einem aber wirklich schwer!!  
Also ich hangele mich vom Startzustand einfach entlang und bekomme dadurch nur ganz wenige Paare (in diesem Fall).
Grundidee so richtig? |
|
| Nach oben |
|
|
Gast
|
| Verfasst am: 23. Aug 2005 22:23 Titel: |
|
|
| so wuerd ich es auch machen |
|
| Nach oben |
|
|
Tobias
Anmeldungsdatum: 15.02.2005
Beiträge: 149
|
| Verfasst am: 10. Sep 2005 13:20 Titel: |
|
|
| Zitat: | | Nur gibt es da einen Trick, bei dem man auf Angabe von Uebergaengen in unerreichbare Zustaende (vom Startzustand aus nicht erreichbar?!?) verzichten kann, den blicke ich nicht und er hat mir in der letzten Klausur den Kopf gekostet |
Ich glaube bei deinem "Trick" geht es um die Tatsache, dass ein DFA über dem Alphabet {a,b,c} nicht wohldefiniert ist, wenn nicht jedem Zustand a, b und c Transitionen zu einem Nachfolge-Zustand zugeordnet sind. Bei einem NFA ist dies nicht notwendig. Bei der Potenzmengenkonstruktion fügt man deshalb einen nicht-akzeptierenden Sackgassen-Zustand hinzu (als leere Menge bezeichnet), der im NFA nicht vorhandene Transitionen auffängt.
Dies kann aber nicht das Problem gewesen sein, denn diese Übergänge kann man ruck zuck ergänzen und wirken sich auch nicht auf die Komplexitätssteigerung des Potenzautomaten aus.
Ich habe das Ding mal konstruiert und komme auf 6 Zustände. Hoffentlich ist das richtig. |
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
| Verfasst am: 12. Sep 2005 17:28 Titel: |
|
|
Ich weiß nicht, ich habe halt die ganze Potenzmenge konstruiert und das dauerte ewig.
Ist auch egal, habe jetzt bestanden |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
