Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität 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.

Bearbeitet: Was passiert bei $n>m$?

Sat, 10 Oct 2015 06:00:49 +0000

Was würde passieren, wenn n größer als m wäre? Dann gäbe es ja z.B. eine Situation $(s_1, d, k_0)$, die nicht definiert wäre, wobei wir uns ja in einem Endzustand befinden. Das wäre dann ungültig, weil kein entsprechender Zustandsübergang definiert ist, unabhängig davon, dass man sich schon in einem Endzustand befindet, oder? Das ist mir grad noch nicht ganz klar. Sonst waren es ja meistens Fälle, in denen ich mich bei ungültigen Wörtern nicht "weiterbewegen kann", während ich mich in einem Nicht-Endzustand befinde. Danke schonmal!

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: 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)