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 turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant 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 huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
68 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
...