Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2011-H-01

Beantwortet: Aufgabe 1

Fri, 19 Mar 2021 15:34:29 +0000

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)

Beantwortet: Trick für den 2. Schritt?

Tue, 29 Sep 2015 09:45:42 +0000

Hallo,

die Frage verstehe ich ehrlich gesagt nicht wirklich.

Du musst die Felder, in denen bereits X0 steht nicht noch einmal betrachten. Die können sich nicht mehr verändern. Du musst in jedem Schritt nur die noch leeren Felder überprüfen, solange bis sich nichts mehr ändert.

Wenn du was anderes meintest, formuliere die Frage doch bitte etwas genauer.

Zusatz: Wenn du in der 2. Iteration (also für X1) schon einige Felder untersucht hast und diese leer geblieben sind, so musst du sie in diesem Durchgang nicht noch einmal überprüfen, sondern erst für X2 dann wieder.

Gruß,

Julian (Tutor)

Beantwortet: Wie kommt man bei $(s_1,s_6)$ auf $X_3$?

Tue, 29 Sep 2015 09:43:44 +0000

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)