Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in HU-2-1

Beantwortet: Wieso handelt es sich bei dem Automat in a) um einen nEA?

Mon, 18 Nov 2019 09:17:10 +0000

Hallo!

Der Automat ist an mehreren Stellen nicht deterministisch.

Zum Einen, wie du schon schreibst, ist beispielsweise im Zustand s2 nicht definiert, was passiert, wenn eine 1 eingelesen wird.

Zum Anderen ist nicht eindeutig, in welchen Zustand der Automat wechselt, wenn sich der Automat in s0 befindet und eine 0 eingelesen wird.

Beides sind Merkmale für nichtdeterministische endliche Automaten.

Viele Grüße

Sebastian Frey (Tutor)

Beantwortet: Zusammensetzung des DEA nicht verständlich

Sun, 14 Jan 2018 08:28:40 +0000

Hallo,

wenn wir einen nichtdeterministischen Automaten deterministisch machen wollen, beginnen wir immer mit unserem Startzustand, der in der Regel s0 ist.
Danach arbeiten wir aber nicht die anderen Zustände des NEA ab. In unserer Übergangstabelle steht, welche Zustandsmengen erreicht werden, wenn wir im Zustand s0 eine Eingabe von 0 bzw. 1 erhalten ({s0,s1} bzw. {s0}). Nun nehmen wir alle Zustandsmengen in die linke Seite der Tabelle auf, hier also nur {s0,s1}, da wir für s0 ja bereits im ersten Schritt die Zustandsübergänge bestimmt haben, und gehen analog zu s0 vor. Dies tun wir, damit für jede Zustandsmenge in unserer Tabelle (die jeweils einen Zustand in unserem DEA darstellt) für jede Eingabe der Folgezustand (hier noch eine Menge von Folgezuständen) definiert ist. Da jede so erhaltene Zustandsmenge zu genau einem Zustand unseres DEA wird, hat somit jeder Zustand für jede Eingabe genau einen Folgezustand (siehe Definition DEA).

Ich hoffe, ich konnte dir weiterhelfen.

Liebe Grüße

Laura (Tutor)

Beantwortet: Zusammensetzung des DEA nicht verständlich

Wed, 10 Jan 2018 15:10:41 +0000

Hallo,

Die Zustände s1,s2 und s3 kommen bei diesem Automaten nie alleine vor. Egal welche Eingabe man macht, man erreicht immer entweder mindestens zwei Zustände oder keinen. Zum Beispiel wenn wir 0 eingeben erreichen wir zwar s1 aber gleichzeitig auch s0. Somit kommen diese drei Zustände nie einzeln vor, weshalb wir sie auch nicht einzeln betrachten müssen.

Beim Algorithmus zum Umwandeln eines nichtdeterministischen in einen deterministischen Automaten trägt man nur die Zustände in der linken Spalte ab, welche in den anderen beiden Spalten bereits vorkamen.

Ich hoffe, das beantwortet deine Frage.

Viele Grüße,

Julia

Beantwortet: Akzeptiert der nEA nicht auch "010" (Widerspruch zur Aufgabenstellung)

Tue, 22 Sep 2015 09:32:32 +0000

Hallo,

Sie haben Ihre Frage richig beantwortet.

Viele Grüße

Irina (Tutorin)