Hausübung 2 - Aufg. 4 - Minimalautomat

ShowMustGoOn
Neuling
Neuling
Beiträge: 9
Registriert: 19. Apr 2006 09:04

Hausübung 2 - Aufg. 4 - Minimalautomat

Beitrag von ShowMustGoOn »

Leider werde ich aus der ganzen Erklärung im Skript nicht schlau, wie man aus dem gegebenen DFA den gesuchten Minimalautomaten erhält.

Könnte mir jemand von Euch mit anderen (möglichst einfachen :wink: ) Worten erklären, wie man hier vorgehen muss?

Wäre echt nett! Danke schon im Voraus!

Benutzeravatar
Tapion
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 14. Okt 2006 19:16
Wohnort: Darmstadt

Beitrag von Tapion »

also dieses Vorgehen habe ich mir aufgeschrieben:

(1) Eliminiere alle nicht erreichbaren Zustände
(2) Bilde Äquivalezklassen ~ von A.
(2.1) Erstes Kriterium: Unterscheide zwischen akzeptierenden und nicht akzeptierenden Zuständen.
=> ~0: A, Q\A
(2.2) q != q' in A. Bilde neue Klassen, wenn \(\delta(q,a)\) und \(\delta(q',a)\) in verschiedene Klassen führen.
(2.3) Wiederhole (2.2) bis keine neuen Klassen menr entstehen.


Äquivalenzklasse: Menge von Objekten/Dingen (hier: Zuständen) die hinsichtlich bestimmter Kriterien gleich sind (hier: Transitionen führen zu Zuständen verschiedener Äquivalenzklassen)
WS 2010/11 - Tutor GDI 1
SS 2010 - Tutor FGI 1+2

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

er wollte einfach worte und keine altgriechische keilschrift :D

is aber auf seite 30 eigentlich ganz gut erklärt.

man fängt halt beim startzustand an und guckt dann in welche zustände man mit allen verfügbaren transitionen hinkommt. im falle von a kommt man in die zustände 1 und 2, also in den später neuen zustand {1,2}. und für den zustand überprüft man dann wieder in welche zustände man mit allen transitionen von 1 UND 2 kommt und bekommt dann wieder einen neuen zustand raus. und das macht man solange bis alle zustände abgedeckt sind und dann noch malen und fertig :)

Benutzeravatar
Tapion
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 14. Okt 2006 19:16
Wohnort: Darmstadt

Beitrag von Tapion »

banshee, was du da schreibst, klingt für mich nach determinisierung eines NFA und nicht nach Minimierung eines DFA ^^.

Und hey, mein Text hat zwar etwas tex dabei, aber nur wegen dem blöden delta. \(\delta(q,a)\) ist eine Transition vom Zustand q ausgehend, aufgerufen durch die Eingabe a.
WS 2010/11 - Tutor GDI 1
SS 2010 - Tutor FGI 1+2

ShowMustGoOn
Neuling
Neuling
Beiträge: 9
Registriert: 19. Apr 2006 09:04

Beitrag von ShowMustGoOn »

@torstensillus: Vielen Dank für Deine Erklärung! Jetzt hab' ich es verstanden. :D

@banshee: Auch Dir danke für Deine Antwort. Ich glaube aber auch, dass Du hier die Determinisierung eines NFA beschreibst. :wink:

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

ohja stimmt...

das mach ich aber generell so, vor allem in klausuren. ich les die aufgaben so wie sie mir gefallen :E

baerchen
Computerversteher
Computerversteher
Beiträge: 382
Registriert: 24. Okt 2006 15:42

Beitrag von baerchen »

ne. du verwirrst andere leute damit du in der klausur besser dastehst ^^
We can do this the hard way or my way ...which is basically the same thing!

Antworten

Zurück zu „Archiv“