Lösung unnötig kompliziert?

Question

Also ich finde die Lösung komisch und unnötig kompliziert.

 

Es müsste doch einfach folgendes gehen:

 

$(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$

$(s_0, a, k_0) \rightarrow (s_1, k_0)$

$(s_1, a, k_0) \rightarrow (s_1, A)$

$(sa, b, A) \rightarrow (s_0, \lambda)$

 

Damit bleibt der Automat deterministisch und ist kürzer. Jetzt könnte ich noch $s_e$ streichen, wenn ich $s_0$ zum Endzustand mache, ich mag aber die Darstellung mit $s_e$, weil man schneller sieht, wann man fertig wäre.

 

Testwort $\lambda$:

 

$$(s_0,\lambda,k_0) \rightarrow (s_e,k_0)$$

 

passt. Testwort $aab$:

 

$$(s_0,aab, k_0) \rightarrow (s_1, ab,k_0) \rightarrow (s_1,b,A) \rightarrow (s_0,\lambda,k_0) \rightarrow (s_e,k_0) $$

 

passt auch. Testwort $aabaab$:

 

$$(s_0,aabaab, k_0) \rightarrow (s_1, abaab,k_0) \rightarrow (s_1,baab,A) \rightarrow (s_0,aab, k_0) \\\rightarrow (s_1, ab,k_0) \rightarrow (s_1,b,A) \rightarrow (s_0,\lambda,k_0) \rightarrow (s_e,k_0)$$

 

Weitere Testwörter sind überflüssig.

 

 

 

Ist das richtig?

 

Comments

Kleine Nachfrage zu meinem Automaten. Angenommen ich lasse $s_e$ weg und mache, $s_0$ zum Endzustand. Wäre dann bei $(s_a,b,A) \rightarrow (s_0, \lambda)$ auch Schluss??? Weil dann wäre er nicht deterministisch. Ich weiß jetzt nur nicht, ob am Ende immer $(s_e,k_0)$ stehen muss oder ob der Automat auch mit $(s_e,\lambda)$ fertig wäre, wenn im Keller sonst nichts mehr drin ist außer $k_0$?

---

Bei $(s_1,b,A) \rightarrow (s_0,\lambda)$ wäre dann Schluss, wenn das Wort fertig abgearbeitet wäre. Warum wäre dieser dann nicht-deterministisch?
$\ldots \rightarrow (s_e,\lambda)$ bedeutet ja nur, dass Sie in diesem Übergang das vorherige Symbol aus dem Keller gelöscht haben, das bedeutet nicht, dass im Keller nichts mehr steht. Wenn Sie $\ldots \rightarrow (s_e,k_0)$ haben, dann wissen Sie, dass der Keller nun leer ist.
Prinzipiell gilt folgendes: Beim Kellerautomaten müssen Sie immer das ganze Wort abarbeiten, wenn Sie am Ende in einem Endzustand sind, dann gehört das WOrt zur Sprache, wenn nicht, dann gehört es nicht zur Sprache. Was im Keller steht, ist egal, der Keller muss zur Akzeptanz eines Wortes nicht abgearbeitet sein.
Viele Grüße
Friederike Pfeiffer

Answer 1

"Es müsste doch einfach folgendes gehen:

$(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$

$(s_0, a, k_0) \rightarrow (s_1, k_0)$

$(s_1, a, k_0) \rightarrow (s_1, A)$

$(s_a, b, A) \rightarrow (s_0, \lambda)$"

 

Sie müssten hier folgendes ändern: 

$$(s_a, b, A) \rightarrow (s_0, \lambda)$$ 

zu 

$$(s_1, b, A) \rightarrow (s_0, \lambda)$$

 

Dann würde es so funktionieren. Der einzige wirkliche Unterschied zwischen Ihrer Lösung und der Musterlösung ist, dass Sie, wenn $aab$ gelesen wurde, in $s_0$ gehen und von dort entweder weiter machen, falls das Wort noch nicht fertig abgearbeitet wurde, oder von dort in $s_e$. 

In der Musterlösung gehen wir zuerst in $s_e$ und, falls das Wort noch nicht fertig abgearbeitet wurde, wieder in $s_0$. Das macht den einen Zustandsübergang mehr aus. 

 

Aber vorsicht, auch Ihre Lösung ist nicht-deterministisch wegen: 

$$(s_0, \lambda, k_0) \rightarrow (s_e, k_0),\\ (s_0, a, k_0) \rightarrow (s_1, k_0)$$

 

Wenn Sie $s_0$ zum Endzustand machen, dann wären Sie wieder deterministisch. 

 

Viele Grüße

Friederike Pfeiffer

Comments

Ok, das mit $s_a$ war ein Tippfehler.
$(s_0, \lambda, k_0) \rightarrow (s_e, k_0)\\ (s_0, a, k_0) \rightarrow (s_1, k_0)$
Kann ich irgendwie garnicht nachvollziehen, warum das nicht-deterministisch ist.
Im Zustand $s_0$, wenn er $a$ liest, geht er in $s_1$ und wenn, das Wort zu Ende ist oder ein leeres Wort da ist, geht er in den Endzustand. Was ist da nicht-deterministisch?

---

$(s_0, \lambda, k_0)$ bedeutet, dass der Automat IMMER, wenn im Keller $k_0$ steht, diesen Übergang nutzen darf. Wenn er also ein $a$ liest, nimmt er den ersten und den zweiten gleichzeitig und ist somit nichtdet. (Wenn er ein $b$ liest, ist klar, dass er den Lambda-Übergang nehmen muss, weil es keinen weiteren Übergang für $b$ gibt.)
Viele Grüße
Lukas König

---

Das verstehe ich nicht, wieso kann er in den Übergang mit lambda gehen, wenn er $b$ liest? $b$ ist doch kein leeres Wort? Und wie könnte ich es dann machen, dass er $\lambda$ akzeptiert, aber das Wort $b$ alleine nicht?

---

$\lambda$ bedeutet hier einfach, dass an dieser Stelle nichts gelesen wird, das heißt ich kann überall einen $\lambda$-Übergang machen, um beispielsweise den Zustand zu wechseln. Sie lesen an dieser Stelle nicht $b$, sondern bleiben vor $b$ stehen und lesen erst anschließend im nächsten Zustand $b$.
"Und wie könnte ich es dann machen, dass er $\lambda$ akzeptiert, aber das Wort $b$ alleine nicht?" - was meinen Sie damit?
Viele Grüße
Friederike Pfeiffer

---

Wie mach ich dann die Übergangsfunktion, wenn der Automat das Wort $w = \lambda$, aber nicht das Wort $w = b$, akzeptieren soll, wenn der Automat auch für das Wort $w = b$ in die Lambda Funktion gehen kann und das dann fälschlicherweise akzeptieren würde?

---

Ganz verstehe ich Ihre Frage immer noch nicht, tut mir leid. Meinen Sie, wie ich $\lambda$ akzeptieren kann, aber ein einzelnes Wort $b$ nicht? Sie können zum Beispiel einen $\lambda$-Übergang machen: $(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$
Oder Sie definieren $s_0$ als Endzustand und gehen mit der ersten "richtigen" Eingabe in einen anderen Zustand: $(s_0, b, k_0) \rightarrow (s_1, b)$ Meinen Sie das so?
Viele Grüße
Friederike Pfeiffer

---

Andere Frage, die sich darauf bezieht:

MUSS man nicht $(s_0, b, k_0) \rightarrow (s_1, b)$ für den Kellerautomaten definieren? Der Fall, dass $b$ in einen leeren Automaten kommt ist gar nicht definiert. Darf das sein?

---

Mir ist noch nicht ganz klar, was Sie wissen wollen... Was soll das heißen, "dass $b$ in einen leeren Automaten kommt"?
Viele Grüße
Lukas König

---

Wenn eine mögliche Konfiguration nicht definiert ist, bleibt die Turingmaschine stehen und das Wort wird nicht akzeptiert. Dein Übergang wäre hier auch falsch, denn wenn nichts im Keller ist, müssen erst 2 $a$'s kommen, erst dann darf ein $b$ im Wort vorkommen. Wenn also bei einem leeren Keller ein $b$ kommt, darf das Wort nicht mehr akzeptiert werden.
Viele Grüße
Patrick(Tutor)