Zustand s5 unnötig

Question

Hallo,

meiner Meinung nach ist in der Musterlösung bei dem dEA der Zustand s5 unnötig, da dies sowieso nie Auf eine Endkonfiguration führen kann und keinen Mehrwert bringt. Lediglich der obere Zweig (s0, s1, s2, s4) erkennt das Muster. Daher kann der Zustand s5 und die Kanten dazu gestrichen werden.

Ist meine Annahme richtig?

 

Answer 1

Hallo Richard,

nein, diese Annahme ist nicht richtig. Einem deterministischen endlichen Automaten kann jedes Wort aus E* als Eingabe übergeben werden. Erst sobald das Wort "abgearbeitet" ist entscheidet sich, ob das Wort akzeptiert wird oder nicht, nämlich ob der dEA in einem Endzustand stoppt oder nicht. Ich glaube, dass dir das noch nicht ganz klar ist.

Zudem: Bei einem dEA muss in jedem Zustand für jedes Eingabesymbol klar sein, was zu tun ist. Würde man nach deiner Anmerkung also die Kanten Streichen, so wäre dies kein dEA mehr.

Nun eine kurze Erklärung für den Zustand s5:

Dieser Zustand ist eine Art nicht-akzeptierender Sackgassenzustand, d.h. ab hier ist klar, dass - egal welche Eingabe noch kommen mag - das Wort nicht mehr akzeptiert wird. Du erkennst ihn daran, dass er nicht mehr verlassen werden kann (alle Elemente aus E führen wieder in s5) und kein Endzustand ist.

Gruß

Philip (Tutor)

 

Comments

Danke Philip,

das hat mir für das Verständnis weiter geholfen. Ich dachte es wäre ausreichend nur zu definieren, welche Schritte erlaubt sind. Sofern ein Schritt nicht definiert ist und der gemacht werden soll, dass dann klar ist, das es nicht erkannt werden kann. Aber so wie du es sagst, muss ich dem EA immer zeigen was er machen soll in den jeweiligen Zustand, auch wenn er dadurch in eine "Sackgasse" kommt.