Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Endlicher Automat; Ich verstehe den Algorithmus nicht

+1 Punkt
170 Aufrufe

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. indecision

Danke für eure Hilfe!!!

Gefragt 14, Feb 2016 in SAA-1-1 von ukejy ukejy Lernwillige(r) (210 Punkte)  
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

2 Antworten

+2 Punkte
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)
Beantwortet 14, Feb 2016 von urdnp urdnp Tutor(in) (103,400 Punkte)  
Vielen Dank! lg :)
+2 Punkte
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)
Beantwortet 14, Feb 2016 von ukean ukean Tutor(in) (103,140 Punkte)  
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
...