Aufgabe 1

Question

Hallo,

kann es sein das bei der Minimierung des DEA man beim ausfüllen der Tabelle auf zwei unterschiedlich markierte Felder kommt. Also bspw. bei S3 und S5 kann ich ja s1 und s3 oder s3 und s4 vergleichen. Bei s1/s3 komme ich auf ein X1 markiertes Feld, bei s3/s4 auf ein X2 markiertes Feld.

Ich bin grade etwas verwirrt. Ich hab mich nun immer am kleineren Zustand orientiert und bin aufs richtige Ergebnis gekommen. Bloß frage ich mich, ob ich etwas falsch mach oder ob das wirklich passieren kann? Und wie ich damit umzugehen habe, da mir das noch nicht in den Tuts oder Übungsbüchern unterlaufen ist.

LG und Vielen Dank!

Answer 1

Hey uuiya,

natürlich kann das sein. Du hast ja sozusagen mehrere Iterationen, in denen du die Tabelle immer wieder komplett durchläufst und jedes offene Feld erneut überprüfst. Findest du beispielsweise in der dritten Iteration ein Zustandspaar, welches auf ein bereits markiertes Feld zeigt, so markierst du das Feld dieses Zustandspaares mit X₃. 

Dabei spielt keine Rolle, ob das bereits markierte Feld mit X₀, X₁ oder X₂ markiert ist - es geht nur darum, ob es markiert ist oder nicht. 

Achtung: Wenn du dich bspw. in der dritten Iteration und weiter unten in der Tabelle befindest und ein Zustandspaar findest, welches auf ein Feld zeigt das weiter oben bereits mit X₃ markiert wurde (also in der selben "Iteration"), so wird dieses noch nicht mit betrachtet. Das würde man dann erst beim nächsten Durchlauf, also in der 4. Iteration, mit X₄ markieren.

Beste Grüße,

Martin (Tutor)

Comments

Hey Martin,
super schonmal danke!!

Zu deinem Achtung:
Aber bspw. wenn ich in der Iteration 1 bin und in der vorletzten Zeile und ich treffe mit einem Variablenpaar auf ein x1 markiertes Feld, welches weiter oben steht. Aber mit dem anderen Variablenpaar auf ein x0 markiertes Feld was weiter unten steht. Wie gehe ich dann vor? Ich hab es dann als x1 markiert was auch richtig war. Aber warum?

Liebe Grüße und vielen Dank!

---

Hey,
das ist ein super Beispiel, warum es wichtig ist, immer beide Zustandspaare zu überprüfen. In deinem Fall ist die Markierung mit x1 richtig. Das erste betrachtete Paar (bspw. für Eingabe einer 0), welches auf ein weiter oben mit x1 markiertes Feld zeigt, betrachten wir quasi noch gar nicht. Stell dir vor, dass wir einen Durchlauf immer erst ganz am Ende "verbuchen", also bevor wir in den nächsten Durchlauf starten. Erst dann werden die Markierungen, in diesem Falle x1, für uns sichtbar und relevant. Das ist auch der Grund, warum du das Feld dann mit x1 markierst: Du befindest dich in Iteration 1 und dein zweites Zustandspaar zeigt auf ein Feld x0.
Soweit verständlich? :)

---

Hey,

ich denke schon, ja danke!! D.h. wenn ich in Interation 1 bin betrachte ich eigentlich nur die Felder welche mit x0 markiert wurden da die mit x1 markierten Felder eigentlich noch nicht sichtbar für mich sind, oder?

Und nochmal ganz kurz dass ich auch weiss das wir von der selben Interation 1 sprechen: Interation 1 = Erster Durchlauf nachdem wir die Felder mit X0 markiert haben?:D

---

Exakt so war es gemeint, sehr gut :) Entsprechend betrachtest du in Iteration n immer nur die Felder, die mit höchstens X(n-1) markiert sind. Also bspw. im dritten Durchlauf die Felder mit X0, X1 und X2.
Und richtig, das wäre die erste "Iteration". Das Wort dient hier aber nur dazu, es anschaulicher zu machen und ist keineswegs als formal korrekt zu betrachten. Aber ja, nachdem wir unsere X0 Felder markiert haben, starten wir sozusagen mit dem ersten Durchlauf / der 1. Iteration. :)

---

Top, vielen Dank für deine Zeit und die Geduld ;)