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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
60 Aufrufe

Heyho,

warum wird denn in der 1b) bei der Zustandsüberführungstabelle die Zustände s2 und s3 nicht mit aufgeommen?

Über Antworten wäre ich dankbar!

Gruß

 

in SAA-1-1 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

das liegt an dem Algorithmus, ich versuche es mal umgangssprachlich zu erklären. Du bildest die Zustandsüberführungstabelle, indem du mit dem Startzustand anfängst, und ausgehend von allen möglichen Eingaben die erreichbaren Zustände in die Zellen rechts daneben schreibst.

Alle noch nicht schon links vorhandenen Zustandsmengen schreibst du nun nach links. In dem Fall wurden diese Zustände jedoch nicht direkt unter den Startzustand geschrieben, sondern 3 Zellen tiefer, das mag vielleicht irritieren. 

Ausgehend von s(o) steht also in der Tabelle noch {s(2),s(3),s(4)} und die leere Menge.

Nun muss also {s(2),s(3),s(4)} näher betrachtet werden, also alle erreichbaren Zustände von allen diesen Zuständen. Daraus ergeben sich die neuen Zustandsmengen {s(4)} und {s(1)}. Diese werden nun betrachtet und so weiter.

Die Zustände s2 und s3 werden jedoch nie "alleine" erreicht, deshalb stehen sie auch nicht in der Tabelle. Sie müssten nur in der Tabelle auf der linken Seite alleine vorkommen, wenn sie beispielsweise von Zustand s(4) direkt und alleine erreicht werden könnten. Dies ist jedoch nicht der Fall.

Vielleicht hilft dir auch Tutorium 2 Folie 6 weiter, dort stehen dann auch nur die Zustände als gesamte Menge und nicht noch aufgeteilt in der Tabelle.

Ich hoffe, ich konnte dir helfen! Viel Erfolg noch und viele Grüße.

Felix (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
warum s2 in endzustands-menge aber nicht doppelt umkreist
...