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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
117 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)  
...