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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
2.8k 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 :)

 

in AU-2-3 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
1 0
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
0 0
Wieso ist denn bei Tut 2 auf Folie 17 der Kellerautomat trotz Lambda-Übergang deterministisch ?
...