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 nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
572 Aufrufe

Dieser Post wurde der Übersichtlichkeit halber erstellt, um die alternativen Lösungsvorschläge aus dem alten ILIAS-Forum nicht überzubetonen. Wenn Sie neue alternative Lösungsvorschläge diskutieren wollen, sollten Sie eine neue Frage erstellen - und NICHT hier posten!

 

in 2012-N-03 von uafjv uafjv Tutor(in) (168k Punkte)  

3 Antworten

0 Pluspunkte 1 Minuspunkt

Hallo,

A3 a)

Kann ich (s1, 1,k0) nach (s1,1k0)

              (s1,1,1) nach (s2, λ)

              (s2,λ,k0) nach (se,λ)

               anstatt

               (s1,1,k0) nach(s2,k0)

               (s2,1,k0) nach (se,k0)

Danke!

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Hi,

ja, das müsste gehen, wobei du dir keinen letzten Schritt auch sparen könntest indem du s_2 als Endzustand definierst.

Gruß,
Jonas B. (Tutor)
0 Pluspunkte 1 Minuspunkt

Ich hab mir zu der Aufgabe überlegt einfach für jede 0 zwei a's in den Keller zu schreiben und dann mit jeder 1 wieder ein a zu löschen.

Darf man prinzipiell bei einem Kellerautomaten 2 Zeichen für ein gelesenes in den Keller schreiben?

Hatte mir das ungefähr so gedacht (wahrscheinlich so nicht ganz richtig, aber dass meine Idee verständlicher wird):

(s0, 0, ko) -> (s0, aako)

(s0, 0, 0) -> (s0, aaaa)

(s0, 1, ko) -> (s2, ko)

(s0, 1, a) -> (s1, lambda)

(s1, 1, a) -> (s1, lambda)

(s1, 1, ko) -> (s2, ko)

(s2, 1, ko) -> (se, ko)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
1 0
Nein, die einzigen erlaubten Operationen auf dem Keller (für einen einzelnen Übergang) sind:

- nichts tun

- oberstes Zeichen löschen (nur bei nicht-leerem Keller)

- ein einziges Zeichen schreiben.

Deine Idee, pro 0 zwei a in den Keller zu schreiben,  könnte man vermutlich über einen zusätzlichen Zustand + λ - Übergang realisieren.

Tobias (Tutor)
0 Pluspunkte 1 Minuspunkt
Guten Morgen,

meine Idee war folgende:

1. Schreibe alle 0en in den Keller
(so,0,ko) -> (s1,0ko)
(s1,0,0) -> (s1,00)

2. Gehe wieder hoch und überschreibe dabei für jede 1 eine 0 mit einem e
(s1,1,0) -> (s1,e)

3. Sobald wieder angekommen lösche pro 1 ein e
(s1,lambda,k0) -> (s2,k0)
(s2,1,e) -> (s2, lambda)

Wäre das denn soweit zumindest korrekt?

Mein Problem ist jetzt, dass ich äquivalent zum * bei den Turingmaschinen eine Möglichkeit bräuchte zu erkennen, dass nichts mehr auf dem Kellerband steht obwohl ich "unten" bin.

Ich hoffe es wir einigermaßen klar, wo mein Problem liegt.

Vielen Dank!
von uafjv uafjv Tutor(in) (168k Punkte)  
1 0
Das funktioniert so leider nicht, da du die wesentliche Eigenschaft eines Kellers/Stacks nicht beachtest: Man kann nur auf das oberste Element zugreifen, daher funktioniert Schritt 1 noch, aber wenn direkt nach dem ersten Übergang gemäß Schritt 2 noch eine 1 eingelesen wird, dann befindet man sich in (s1, 1, e). Das e hast du ja im vorherigen Übergang geschrieben. Dafür gibt es aber keinen Übergang und der Kellerautomat würde die Eingabe nicht akzeptieren. Um an die 0er unter diesem e ranzukommen, müsstest du das e erst löschen und dann geht dir die Information verloren... Eine Möglichkeit, in den Keller runter zu "spulen" ohne die oberen Einträge zu löschen, gibt es nicht!

Tobias (Tutor)
...