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

Beantwortet: Vereinfachung beim EA möglich?

Tue, 22 Sep 2015 06:51:53 +0000

Hallo,

das ist nicht möglich. Zustand d ist ein sogennanter "Senkenzustand". Die Einführung dieses Zustandes ist zwingend notwendig, da man in diesem Zustand landet, wenn man mehr als zwei Einsen nacheinander eingibt. Und gerade dann, wenn man mehr als zwei Einsen nacheinander eingibt, darf nach Aufgabenstellung mein Wort ja nicht mehr zur Sprache gehören.

Dies gewährleiste ich durch Zustand d, aus dem ich nicht mehr rauskomme, wenn ich mindestens einmal drei oder mehr Einsen nacheinander eingegeben habe. Somit kann kein Endzustand mehr erreicht werden (d selbst ist kein Endzustand) und alle möglichen Wörter, die mehr als zwei aufeinanderfolgende Einsen enthalten, werden nicht akzeptiert.

Zur Info: Ein Automat akzeptiert ein Wort nur, wenn man nach Eingabe des Wortes in einem Endzustand landet.

Max (Tutor)

Beantwortet: Endlosschleife beim EA ?

Tue, 22 Sep 2015 06:51:02 +0000

Ich habe den Eindruck, du siehst die Aufgabe des EA darin, die Eingabe in Teilstücke aufzuteilen (immer nach dem 001). Der EA soll aber überprüfen ob die gesamte Eingabe (als ein einziges Wort) zu der Sprache gehört oder nicht. Das heißt, auch Eingaben wie 10010001 werden als ein einziges Wort behandelt! Zu Beginn der Eingabe/des Wortes startet der Automat immer im Startzustand (hier a).

Wenn in Zustand d eine 1 eingegeben/gelesen wird, dann muss, wenn die Eingabe in der Sprache sein soll, noch mindestens 001 folgen. Insofern ist die Situation nach dieser 1 die selbe wie beim allersten Zeichen der Eingabe. Wenn in d eine 0 eingegeben wird, dann ist braucht man "nur" noch 01, da man die erste 0 ja gerade gelesen hat. Deshalb wechselt man nach b und nicht nach a.

Tobias (Tutor)

Beantwortet: Bennenung der Elemente mit Groß-/Kleinbuchstaben ?

Tue, 22 Sep 2015 06:49:02 +0000

Hallo,

Ob groß oder klein ist egal. In den VL-Folien findest du auch Zustande, die mit Zahlen benannt wurden. Sieh es einfach wie eine Variable in der Mathematik: es sollte halt eindeutig sein.

Basti (Tutor)

Beantwortet: Gibt es mehrere richtige Lösungsmöglichkeiten für EA?

Tue, 22 Sep 2015 06:46:59 +0000

weitere Ergänzung:

Wie Antonio richtig gesagt hat, können Sie den Nullpfeil von C auf C nicht löschen, da ihr Automat dann nicht mehr das Wort 0001 erkennt. Sie können die von Ihnen vorgeschlagenen Pfeil ergänzen. Er deckt aber nichts ab, was durch den Automaten in der Musterlösung nicht auch schon abgedeckt wäre, und, ganz wichtig, Ihr AUtomat wäre dann nichtdeterministisch und demnach zwar in dieser AUfgabenstellung ok, aber wenn explizit nach einem deterministischen Automaten geftragt wurde, dann müssen Sie auch solch einen angeben.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König