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

1 Pluspunkt 0 Minuspunkte
25 Aufrufe
Hallo,

wie kommt man denn bei der Ausführung des Algorithmus bei dem Feld von $(s_1, s_6)$ auf die $X_3$?

Meine Vorgehensweise war, dass man zunächst $s_2$ und $s_7$ wählt, dann wählt man $s_1$ und $s_6$, im nächsten Schritt wählt man $s_0$, $s_4$ und $s_5$. Wenn ich dann soweit alle $X_0, X_1, X_2$ eingetragen habe, und im letzten Schritt $s_3$ wähle, dann ist in den entsprechenden Zellen bereits alles aufgefüllt. Und wieso trägt man dann die $X_3$ in ein Feld mit einem von $s_3$ verschiedenen Paar ein?

Vielen Dank
in 2011-H-01 von uafjv uafjv Tutor(in) (168k Punkte)  
Bearbeitet von

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

du solltest dir vielleicht noch einmal genau den Algorithmus aus der Vorlesung verinnerlichen.

Wie du im 1. Schritt richtig erkannt hast markierst du alle Paare an Zuständen mit x0, bei denen einer ein Endzustand ist und der andere nicht.

Jetzt schaust du in die Tabelle für die Zustandsübergänge und suchst alle Paare heraus bei denen du durch Eingabe von 0 ODER 1 auf ein bereits markiertes Paar (x0) kommst, also z.B. kommst du mit dem Paar s0, s1 durch Eingabe einer 0 auf das Paar s1, s5, was bereits durch ein x0 markiert ist, deshalb schreibst du für das Paar s0, s1 ein x1 ins Feld...
das gleiche machst du dann für die x2, wobei du hier auf die mit x1 markierten Felder achtest und für x3, wo du auf die x2 achtest.

Da du jetzt beim Zustandspaar s1, s6 durch Eingabe einer 0 auf Zustandspaar s3, s5 kommst, was mit x2 markiert ist kommt hier demzufolge die x3 her. Vorher dürfte da also nichts drinstehen, weil du auch bei einer Eingabe von 1 auf Zustandspaar s2, s7 kommst, welches nicht markiert ist.

Gruß

Johannes (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
" z.B. kommst du mit dem Paar s0, s1 durch Eingabe einer 0 auf das Paar s1, s5, was bereits durch ein x0 markiert ist, deshalb schreibst du für das Paar s0, s1 ein x1 ins Feld... "

Wenn ich mir das so anschaue, ist doch s1,s5 nicht mit X0 markiert (keiner von beiden ist ja auch ein Endzustand!). Ich schreibe in das Paar s0,s1 doch deswegen ein X1, da sie beide mit einer 1(!!!) auf das Paar s2,s4 führen, da DIESES Paar bereits mit X0 markiert wurde (x2 ist ja auch Endzustand und x4 nicht).

Beste Grüße
0 0
Ja du hast vollkommen Recht, ich dachte beide Eingaben 0 und 1 würden gehen, aber hab mich bei der 0 wohl in der Zeile verguckt... also du schreibst in das Paar s0,s1 ein x1 weil du durch Eingabe einer 1 auf s2,s4 kommst was bereits durch x0 markiert ist.

Gruß

Johannes (Tutor)
...