Wann Kellerautomat deterministisch/nichtdeterministisch?

Question

Zitat

Das Problem bei dieser Variante ist dann aber, dass es kein deterministischer KA mehr ist, wie es in der Aufgabe gefordert wurde, da in Zustand s0 für das Kellerzeichen k0 sowohl bei a als auch bei lambda ein Übergang definiert wäre.

Ich verstehe nicht, was hier der Unterschied zu dem Teil der Musterlösung ist, in dem in Zustand s1 für das Zeichen b sowohl bei a als auch bei b ein Übergang definiert ist.

Es wäre toll, wenn mir nochmal jemand erklären könnte, warum das eine den Automaten nicht deterministisch machen soll und das andere nicht. Vielen Dank!

 

Answer 1

Hallo,

das Zitat, welches Sie hier nennen, bezieht sich auf das Hinzufügen des folgenden Übergangs: (s0, lambda, k0) -->... .
Da der Automat aber auch den Übergang (s0, a, k0) --> ... enthält, wäre der KA somit nichtdeterministisch.

Bei folgenden Aussage "Ich verstehe nicht, was hier der Unterschied zu dem Teil der Musterlösung ist, in dem in Zustand s1 für das Zeichen b sowohl bei a als auch bei b ein Übergang definiert ist." verstehe ich leider nicht, worauf Sie sich beziehen.

Freundliche Grüße
Friederike Pfeiffer

Comments

Ok, dann versuche ich mich anders zu erklären:

Was ist mit den Übergängen:

(s1, a, b) ---> ...

(s1, b, b) ---> ...

tritt dort nicht dasselbe Problem auf, wie bei den Übergängen mit s0 und k0, die Sie genannt haben?

---

Nein, Sie können nicht davon ausgehen, dass nur, weil im Keller das gleiche Symbol steht, der Automat nichtdeterministisch wird. Sie können hier NIE wählen, welchen der beiden Übergänge Sie nehmen. (s1, a, b) --> ... können Sie nur dann wählen, wenn im Keller ein b steht UND wenn ein a eingegeben wird. (s1, b, b) --> können Sie nur dann wählen, wenn im Keller ein b steht UND wenn ein b eingegeben wird. Demnach machen diese Übergänge den Automaten NICHT nichtdeterministisch.

Bei den Übergängen (s0, lambda, k0) -->... und (s0, a, k0) --> ...können Sie aber sehr wohl wählen, und zwar, wenn im Keller k0 steht und ein a eingegeben wird. Beim Übergang (s0, lambda, k0) -->... bleiben wir einfach vor dem a stehen, lesen lambda (also nichts) und nehmen den Übergang. (Danach müssten wir dann aber das a noch lesen). Lambda bedeutet hier nicht, dass das Eingabewort nur das leere Wort ist, sondern einfach, dass Sie an einer Stelle stehen bleiben und ohne vom Eingabewort etwas einzulesen einen Übergang machen können.

Ich hoffe, dass das nun klarer ist.

Viele Grüße
Friederike Pfeiffer

---

Ah, ok. Dass Lambda nicht nur das leere Wort ist, sondern eben auch das "Stehenbleiben und nichtslesen" hatte ich noch nicht verstanden. Jetzt kann ich es nachvollziehen. Vielen Dank!
Antworten Bearbeiten Drucken Löschen Zensur Gelesen