Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Unterschied Deterministischen und Nichtdeterministischen Kellerautomaten?

+1 Punkt
1,963 Aufrufe

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 :)

 

Gefragt 21, Sep 2015 in AU-2-3 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

+1 Punkt

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)

 

Beantwortet 21, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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 ?
...