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

Beantwortet: wieso beginnt das wort mit 0 und kann nicht mit 1?

Sun, 11 Nov 2018 14:59:12 +0000

Hallo uvlpj,

im Graph der Lösung ist ein Automat dargestellt, der Wörter erkennt, die mit einer $1$ beginnen. Ausgehend vom Startzustand $s_0$ wird mit einer $1$ in den Endzustand $s_1$ gewechselt.

Sollte das Wort mit einer $0$ beginnen, bleibt der Automat in $s_0$.

Du kannst natürlich auch in einen weiteren Nicht-Endzustand wechseln, wenn das Wort mit einer $0$ startet. Dieser Zustand benötigt allerdings wieder Übergänge für die Eingaben $0$ und $1$.

Viele Grüße

Philipp
(Tutor)

Beantwortet: Teil c)

Wed, 11 Jan 2017 09:16:43 +0000

Hallo,

ja, der Übergang muss hier weiterhin angegeben werden, damit der Automat deterministisch bleibt.
Wenn ein Automat deterministisch sein soll, dann muss für jeden Zustand und jede Eingabe genau ein Übergang existieren. Entfernt man hier die Übergänge, ist der Automat folglich nicht mehr deterministisch.

Grüße, Sören (Tutor)

Beantwortet: $\lambda \in L \Leftrightarrow s_0 \in F$?

Tue, 17 Nov 2015 07:44:53 +0000

Wie kommen Sie darauf, dass das leere Wort Teil der Sprache sein soll? Da steht

$$|w|_1 > 0$$

was soviel bedeutet, wie dass die Anzahl der Einsen im Wort größer als 0 sein muss. Dadurch kann das Wort ja nicht leer sein.

(Ich sehe gar nicht, wo Sie ein $\lambda$ in der Aufgabenstellung entdeckt haben.)

Rein prinzipiell haben Sie aber recht: Bei endlichen Automaten gilt, dass das leere Wort genau dann Teil der Sprache des EA ist, wenn der Startzustand gleichzeitig ein Endzustand ist.

Beantwortet: a): andere Übergänge möglich?

Mon, 21 Sep 2015 08:50:37 +0000

Hallo!

Nein, dass ist bei dieser Aufgabe nicht möglich! Wenn du von S aus mit der "0" sowohl in S bleiben als auch nach F gehen kannst (also noch einen "0"-Pfeil von S zu S einfügst), dann ist dein Automat nichtdeterministisch (nEA). In der Aufgabe ist aber ein EA (also ein deterministischer endlicher Automat) verlangt.

Gruß,

Janine (Tutorin)

Beantwortet: c): alternativer Lösungsvorschlag

Mon, 21 Sep 2015 08:48:57 +0000

Dein EA ist kein deterministischer EA (fehlender Übergang für Zustand d und Eingabe 1), erkennt aber als nichtdeterminister EA die geforderte Sprache. Da in der Aufgabenstellung nicht explizit gefordert ist, das der Automat deterministisch sein muss, müsste das ok sein. Zu dem Zeitpunkt, als die Aufgabe im Tut besprochen wurde, war der nichtdeterministische EA vermutlich noch in der Vorlesung dran...

Gruß,

Tobias (Tutor)

Beantwortet: a): Bezeichnung von Startzuständen

Mon, 21 Sep 2015 08:45:20 +0000

Hallo,

im Prinzip kannst du die Zustände und den Startzustand beliebig bezeichnen, wichtig ist, dass die dann auch so bei dem Tupel angeben werden.

Viele Grüße

Christiane (Tutor)

Beantwortet: b): leeres Wort in Sprache - Startzustand als Endzustand?

Mon, 21 Sep 2015 08:44:15 +0000

Hallo Luisa,

das leere Wort liegt in diesem Fall nicht in der Sprache drin, denn es wird durch die Bedingung, dass w mindestens eine 1 hat, ausgeschlossen. Im Grunde muss man die Definition immer folgendermaßen lesen:

Betrachtet werden alle Wörter w aus einer gegebenen Menge (hier: {0,1}* - ich nehme an, das * hat dich irre geführt) MIT der Eigenschaft, dass w mindestens eine 1 hat.

Viele Grüße,

Vivian (Tutor)