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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 1 Minuspunkt
43 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?

 

in END-AC von uyctv uyctv Info-Genie (21.1k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

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)

 

von uyctv uyctv Info-Genie (21.1k Punkte)  
0 0
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.
...