Welche Sprachen akzeptiert ein dPDA mit leerem Stack?

Die Sprachen, die von einem dPDA erkannt werden, kann man einfach anhand der Präfix-Eigenschaft erkennen.
Quelle:
Hopcroft, John E. ; Motwani, Rajeev ; Ullman, Jeffrey D.: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Aufl. München [u.a.] : Pearson Studium, 2002 (Informatik). - ISBN 3-8273-7020-5 S. 291 f.

[@ZitaWupWarframe]

bei L2 wenn wir das wort abba haben, kann das sein dass der automat ein a gelesen hat und denkt schon an der hälfte? aber da kommen noch bab. also das wäre auch ein fall zu zeigen dass die sprache nicht von dem automat akzeptiert wird?

[@SamyaDaleh]

+waa zitang 1. Deterministisch heißt, dass der Automat nur eine Möglichkeit hat für jedes Eingabezeichen in Kombination mit dem obersten Stacksymbol. Denkt er nach dem ersten a schon an die Hälfte? Nicht unbedingt. An der Hälfte möchte er das Stacksymbol vom letzten a zusammen mit dem ersten a der zweiten Hälfte lesen. Also wenn er nach dem ersten a das b sieht, weiß er, dass er nicht bei der Hälfte sein kann. Aber wenn nach dem ersten a ein weiteres a käme, dann wüsste er nicht, ob das zur ersten oder zweiten Hälfte gehört.
2. "ein Fall zu zeigen, dass die Sprache nicht vom Automat akzeptiert wird" nein nein, es ist ganz anders. Du erstellst einen Automaten, der die Sprache akzeptiert, ok? D. h. er akzeptiert sie auf jeden Fall. Die Frage ist, gibt es einen deterministischen Automaten, der die Sprache erkennt. Entweder es gibt einen oder es gibt keinen, dann gibt es nur einen nichtdeterministischen. Du hast aber nicht einen Automaten, der die Sprache nicht akzeptiert, denn sonst ist es einfach ein anderer Automat für eine andere Sprache.