Unterschied Deterministischen und Nichtdeterministischen Kellerautomaten?

Question

Kann nochmal jemand bitte explizit den Unterschied zwischen Deterministischen und Nichtdeterministischen Kellerautomaten erklären? Insbesondere auch was man beim erstellen jeweils anders machen muss.

Danke :)

 

Answer 1

Ein nichtdet. KA zeichnet sich dadurch aus, dass er bei einem Eingabesymbol die "Auswahl" zwischen mehreren Übergangsregeln hat. Dabei betrachtet man nur den Linken Tupel der Übergangsregel (also Links vom Pfeil).

Am Beispiel (unabhängig der Aufgabe):

(s0,1,1) -> (Beliebiger_zustand, Beispielzeichen)

(s0,lambda,1) -> (Beliebiger_zustand, Beispielzeichen)

Sei nun o.B.d.A. das oberste Zeichen im Keller eine 1 und der KA grade im Zustand s0: 

Wenn das folgende Eingasymbol eine 1 ist kann der Automat nun die 1. Übergangsregel verwenden oder aber er ignoriert das Eingasymbol und verwendet den Lamdaübergang (also 2. Übergangsregel) und geht in die entsprechend auf der rechten Seite definierten Zustände.

Da der KA hier die Wahl hat und nicht klar ist, welche Übergangsregel er verwenden muss würde es sich hier um einen nichtdet. KA handeln.

Wichtig ist, hier Lambda richtig zu verstehen. Das heißt NICHT, das es kein Eingabesymbol mehr gibt oder die Eingabe leer ist, sondern dass der Automat die Eingabe schlicht ignoriert. Sprich, der Übergang ist in dem Falle nur noch vom aktuellen Zustand und obersterstem Kellersymbol abhängig, und nicht auch noch vom Eingabesymbol.

Philippe (Tutor)

 

Comments

Ein kurzer Nachtrag an dieser Stelle:

Beachten Sie, dass aber ein Kellerautomat , der einen lambda-Übergang hat, nicht zwangsläufig nichtdeterministisch ist. Die kann häufig so sein, muss es auch nicht.

Andersherum muss ein Kellerautomat auch keinen lambda-Übergang beinhalten, um nichtdeterministisch zu sein.

Wie Philippe schon geschrieben hat, sobald sie die WAHL haben, dann ist der Kellerautomat nichtdeterministisch.

Wenn Sie dazu noch Fragen haben, dann fragen Sie bitte nach. Es ist wichtig, dass Sie den Unterschied verstehen.

Viele Grüße

Friederike Pfeiffer-Bohnen

---

Wieso ist denn bei Tut 2 auf Folie 17 der Kellerautomat trotz Lambda-Übergang deterministisch ?