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

Kategorien

1 Pluspunkt 0 Minuspunkte
130 Aufrufe

Hallo, ich habe eine  Verständnisfrage, die sich auf die Anmerkung zum Nichtdeterminismus des Kellerautomaten bezieht:

Könnte man die erste Zeile des Kellerautomaten (s0, lamda, k0 ) --> (se, k0) nicht auch einfach weglassen, dafür dann s0 ebenfalls als Endzustand definieren und somit verhindern, dass der Kellerautomat bereits schon in der ersten Zeile nichtdeterministisch wird?

Wenn man das nicht dürfte, wäre es schön, wenn jemand kurz erklären könnte, warum man das nicht darf :)

Vielen Dank!

in KEL-AD von uudtm uudtm Lernwillige(r) (360 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo uudtm!

Ja, durch das Weglassen der ersten Übergangsregel und stattdessen der Definition von s_0 als Endzustand würde sich an der Funktionsweise des Kellerautomaten tatsächlich nichts ändern, das wäre also zulässig.

Nichtsdestotrotz bleibt dein Kellerautomat insgesamt nicht-deterministisch (was ja auch im Aufgabentext explizit so gefordert wird) wegen dem in der Anmerkung erwähnten doppelten Übergang von (s_1,a,a) und den Übergängen (s_2,lambda, k_0) gekoppelt mit (s_2, c, k_0).

Ich hoffe, das beantwortet deine Frage!

Viele Grüße,
Janine (Tutorin)
von uedqi uedqi Tutor(in) (109k Punkte)  
...