Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2011-N-03

Beantwortet: alternative Lösung

Thu, 02 Feb 2017 19:12:29 +0000

Hallo,

in der Aufgabe wird nach einem deterministischen Kellerautomaten gefragt.
Da bereits ein Übergang (s1, c, a) -> (s1, lambda) existiert, dürfen Sie keine Lambdaübergänge verwenden.

Beantwortet: Ist auch eine umständlichere Lösung denkbar?

Tue, 29 Sep 2015 10:44:47 +0000

Prinzipiell können Sie das auch so machen, die andere Lösung ist natürlich schöner,weil sie kürzer ist (aber das war hier ja nicht verlangt): Demnach, wenn Ihr Automat sinst richtig ist, dann passt das.

Vielel Grüße

Ihre Übungsleiter

Beantwortet: a): Warum geht KA beim akzeptieren vom leeren Wort im ersten Schritt nicht in s1?

Tue, 29 Sep 2015 10:43:49 +0000

Da s0 auch Endzustand ist, wird das leere Wort direkt akzeptiert. Sie brauchen dazu also nicht s0 zu verlassen. (das müssten Sie nur machen, wenn irgendwelche Wörter am Anfang aufreten können, die Sie nicht akzeotieren dürfen, aber da in s0 ja nur a's und b's eingelesen werden, und jede Kombination aus nur a's und b's zur Sprache gehört, müssen Sie s0 hier nicht verlassen).

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Was passiert bei $n>m$?

Tue, 29 Sep 2015 10:41:46 +0000

Damit ein Wort von einem Kellerautomaten akzeptiert wird, müssen 2 Bedingungen erfüllt sein:

- 1. Das Eingabewort ist vollständig abgearbeitet.

- 2. Der Kellerautomat befindet sich in einem Endzustand.

In dem von dir geschilderten Fall ist der KA zwar in einem Endzustand, aber das "d" könnte mangels eines passenden Übergangs nicht verarbeitet werden -> Bedingung 1 nicht erfüllt, Wort wird nicht akzeptiert.

Tobias (Tutor)

Beantwortet: Muss der Keller nach dem Abarbeiten des Wortes leer sein?

Tue, 29 Sep 2015 10:40:18 +0000

Der Keller muss nach unserer Definition nach nicht leer sein. Sie können dies auch nochmal auf den Folien nachschauen.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: sind 3 Zustände nicht besser?

Tue, 29 Sep 2015 10:38:56 +0000

Ja das ist möglich. Es ist aber sehr wichtig, dass dein weiterer "logischer Aufbau" richtig ist. Du musst beachten, dass die Zustände stimmen und auch der neue Zustand ein Endzustand ist. Ohne die weiteren Übergänge kann ich aber keine genaueren Aussagen machen. Grundsätzlich ist es aber möglich.

Gruß Alexander (Tutor)