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

Zustand s5 unnötig

–1 Punkt
36 Aufrufe

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?

 

Gefragt 24, Okt 2014 in END-AC von uyctv uyctv Info-Genie (19,250 Punkte)  

Eine Antwort

0 Punkte

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)

 

Beantwortet 24, Okt 2014 von uyctv uyctv Info-Genie (19,250 Punkte)  
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.
...