Endlicher Automat; Ich verstehe den Algorithmus nicht

Question

Hallo,

ich war leider das Wintersemester im Praktikum und habe mir den nEA -> dEA Algorithmus von einem Informatiker erklären lassen. Mit dessen Algorithmus komme ich aber bei der Aufgabe 1 b) auf ein völlig anderes Ergebnis, nämlich:

Endliche Automaten

∂	0	1	2
s_0	s_2, s_3, s_4	-	-
s_2, s_3, s_4	s_4	s_1	s_1
s_4	s_4	-	-
s_1	s_2, s_3	-	s_1
s_2, s_3	-	s_1	s_1

Wenn ich nun zusammenfasse komme ich auf:

s'_0 = s_0
s'_1 = {s_2, s_3, s_4}
s'_2 = s_4
s'_3 = s_1
s'_4 = {s_2, s_3}

Und damit auf ein völlig anderes Ergebnis als A' in der Lösung.
Insbesondere in Hinblick auch auf Aufgabe 1 Teil a) ist ein Übergang von s_0 mit 1 oder 2 nicht möglich. Kann das mal jemand erklären, es macht für mich einfach keinen Sinn Übergänge einzubauen die nach dem regulären Ausdruck eindeutig nicht zulässig sind. 

Danke für eure Hilfe!!!

Comments

Ich glaube ich verstehe so langsam, auch die nicht zulässigen Eingaben 1 und 2 werden in der Aufgabenlösung modelliert und führen auf einen Zustand s_5, ich nenne ihn mal den "Fehleingabe-Zustand", denn aus ihm kommt man nicht mehr heraus… Alle Zustände, bei denen ich nun einen - gemacht habe führen da hin.

---

Ja genau, siehe auch meine antowort unten..
Lg

Answer 1

Also du hast in deiner "tabelle" die leere menge als neuen Zustand im dEA vergessen. Dies löst dann dein Problem, da du jetzt von deinem s'0 für jeweils eine 0,1 oder 2 einen übergang hast.

Schau dir dazu auch nochmal die Tut folien an, da ist das auch anschaulicher erklärt.

löst das dein problem?

lg,

maren (tutorin)

Comments

Vielen Dank! lg :)

Answer 2

Hallo ukejy,

so falsch ist deine Lösung doch gar nicht ;)

Zunächst mal zu den "nicht zulässigen Übergängen".

Wie du richtig bemerkt hast, haben wir in unserem nichtdet. Automaten nicht zu jedem Zustand jeden möglichen Übergang definiert (was hier auch kein Problem darstellt). Wenn wir den Automat nun deterministisch konstruieren wollen, müssen wir aber laut Definition von jedem Zustand pro Eingabesymbol genau in einen Folgezustand kommen. Das heißt, dass wir  z.B. auch in s0 zwingend einen Übergang für das Eingabesymbol "1" brauchen. Da dies aber von unserem nichtdet. Automat nicht erkannt werden würde, wollen wir das natürlich auch in unserem deterministischen Automat nicht. Aus diesem Grund führen wir für alle Felder in unserer Minimierungstabelle, in denen wir die leere Menge stehen haben, einen neuen Zustand ein (hier s5). Wenn du dir die Zustandsüberführungsfunktion anschaust, siehst du, dass dieser Zustand ein "Sackgassenzustand" ist, d.h. wenn wir einmal in diesen Zustand gelangen, haben wir keine Möglichkeit wieder herauszukommen, so dass sichergestellt ist, dass der Automat in diesem Fall in keinen Endzustand mehr gelangen wird. Daher erreichen wir den gleichen Effekt wie bei dem äquivlenten nichtdet. Automat.

Übrigens ist die Benennung der einzelnen Zustandsmengen beliebig, so lange du diese dann in der neuen Zustandsüberführungsfunktion richtig anwendest und auch richtig definierst.

Ansonsten kann ich soweit keinen Fehler in deiner Tabelle erkennen (außer die fehlenden Mengenklammern ;)

Ist dir das Prinzip etwas klarer geworden?

Viele Grüße,

Tim (Tutor)

Comments

Vielen Dank für die ausführliche Hilfe!
Die Definition lesen war der richtige Hinweis… :)
Ich hatte übersehen oder vergessen, dass man wirklich alle Übergänge definieren muss. Na besser jetzt nochmal als in der Klausur