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

Beantwortet: Fehler in der MUsterlösung?

Mon, 21 Jan 2019 17:53:58 +0000

Hallo uneib,

Der KA ist deterministisch, da 0 und 1 verschiedene Eingabezeichen sind.
Der Automat wäre nur ndet wenn für die selben Ausgangskonfigurationen verschieden Übergänge existieren würden:

ndet:
δ(s0, 0, k0) = >(s0, 0k0)
δ(s0, 0, k0) = >(s2, k0)

Viele Grüße

Philipp (Tutor)

Beantwortet: Fehler in Lösung?

Fri, 25 Sep 2015 15:12:24 +0000

Nein, die Lösung ist korrekt. Deine Herangehensweise enthält einen Fehler. Ein Wort das noch nicht ganz abearbeitet wurde, wird von einem Kellerautomaten nicht akzeptiert. Ich zitiere hier kurz Tobias:

"Bei det. Kellerautomaten haben wir die Konvention, dass wenn die Eingabe noch nicht vollständig abgearbeitet ist und kein "passender" Übergang definiert ist, der Kellerautomat das Wort nicht akzeptiert."

Wie du richtig erkannt hast, "liest der Automat die Wörter garnicht", das heißt, er lehnt das (falsche) Wort ab. Der Automat muss sich zum akzeptieren in einem Endzustand befinden und das Eingabewort muss vollständig abgearbeitet sein.

Viele Grüße

Felix (Tutor)

Beantwortet: Was passiert wenn in sE noch eine 0/1 kommt?

Fri, 25 Sep 2015 15:11:21 +0000

Bei det. Kellerautomaten haben wir die Konvention, dass wenn die Eingabe noch nicht vollständig abgearbeitet ist und kein "passender" Übergang definiert ist, der Kellerautomat das Wort nicht akzeptiert.

(Bei nichtdet. Kellerautomaten im Prinzip auch, aber hier kann der Automat ja gleichzeitig in mehreren Zuständen, so dass ein fehlender Übergang für einen einzelnen dieser Zustände nicht automatisch bedeutet, dass das Wort nicht akzeptiert wird)

Gruß,

Tobias (Tutor)

Beantwortet: Muss der Keller im Endzustand notwendigerweise leer sein?

Fri, 25 Sep 2015 15:09:18 +0000

Hallo,

kurze Richtigstellung: Der Keller muss NICHT leer sein, damit ein Wort akzeptiert wird. Das Wort muss lediglich abgearbeitet sein.

Viele Grüße

Friederike Pfeiffer-Bohnen

Beantwortet: Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Fri, 25 Sep 2015 15:07:52 +0000

Guten Morgen,

meine Idee war folgende:

1. Schreibe alle 0en in den Keller
(so,0,ko) -> (s1,0ko)
(s1,0,0) -> (s1,00)

2. Gehe wieder hoch und überschreibe dabei für jede 1 eine 0 mit einem e
(s1,1,0) -> (s1,e)

3. Sobald wieder angekommen lösche pro 1 ein e
(s1,lambda,k0) -> (s2,k0)
(s2,1,e) -> (s2, lambda)

Wäre das denn soweit zumindest korrekt?

Mein Problem ist jetzt, dass ich äquivalent zum * bei den Turingmaschinen eine Möglichkeit bräuchte zu erkennen, dass nichts mehr auf dem Kellerband steht obwohl ich "unten" bin.

Ich hoffe es wir einigermaßen klar, wo mein Problem liegt.

Vielen Dank!

Beantwortet: Verständnis zur Angabe des Testworts

Fri, 25 Sep 2015 15:04:49 +0000

Hallo,

die Schreibweise (s,e,k) --> (s',v) bedeutet i.A., dass k ersetzt wird durch v wobei das linkeste Zeichen von v das oberste Kellerzeichen ist (vgl. Folie 3-6). Wenn also die a's lediglich auf die 0er draufgeschrieben werden würden, dann würde der Übergang wiefolgt aussehen:

(s1,1,0) --> (s1,a0)

Da aber in der Aufgabe nur (s1,a) da steht, bedeutet das, dass die 0 im Keller durch ein a ersetzt wird statt durch a0.

Viele Grüße,

Vivian (Tutor)

Beantwortet: Wieso wird hier ein a im Kellerautomat eingeführt?

Fri, 25 Sep 2015 15:03:25 +0000

Das a bedeutet hier übrigens folgendes:

Sie müssen ja für jede 0 zwei 1en schreiben. Zuerst schreiben Sie alle 0en in den Keller. Wenn jetzt eine 1 kommt, dann können Sie ja nicht eine 0 löschen, weil Sie brauchen ja für eine 0 noch eine weitere 1. Also ersetzen Sie die 0 im Keller durch ein a, was sozusagen die Information enthält "es wurde schon eine 1 geschrieben, also brauchen wir noch eine 1, um die 0 komplett zu löschen". Wenn jetzt die nächste 1 kommt, dann wird das a komplett gelöscht und dann haben Sie für eine 0 zwei 1en geschrieben.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König