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

0 Pluspunkte 0 Minuspunkte
119 Aufrufe
Hallo,

falls x=a bei der optimierten Variante der Turingmaschine gilt, läuft die Turingmaschine |vx|+3 Schritte. Bis hierhin ist mir die Lösung klar. Nun ist meine Überlegung:

Falls x=b gilt, läuft die Turingmaschine zuerst die |vx|+3 Schritte und "sieht" dann, dass der letzte Buchstabe ein b ist. Somit läuft die Turingmaschine bis ganz nach links zum ersten Stern (+(|vx|+1) Schritte), dann einen Schritt nach rechts (+1 Schritt) und überschreibt dort das falsch gesetzte a mit einem b. Somit wären das |vx|+1+1 = |vx|+2 Schritte mehr als für den Fall x=a. Also würde so für x=b die Anzahl der Schritte 2|vx|+5 betragen.

Habe ich irgendwo einen Denkfehler?

Vielen Dank im Voraus!

Liebe Grüße
in 2017-N-03 von  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo,

du hast recht, da hat sich ein Fehler in der Musterlösung eingeschlichen. Allerdings ist die Schrittzahl dabei nicht IvxI + 5, sondern IvxI + 6.
schau dir am besten einmal die arbeitsweiese der Turingmaschine bei er Abarbeitung eines Wortes auf dem X-Wizard an (siehe Tabellen in Musterlösung). Wichtig ist dabei, dass der letzte Schritt, das Schreiben von b auch ein Arbeitsschritt der Turingmaschine ist. Ich glaube das Problem ist dabei, dass man einen Schritt hier nicht mit einer Bewegung des Schreib-/Lesekopfes verwechselt werden darf.

Liebe Grüße

Verena (Tutor)
von updrq updrq Tutor(in) (104k Punkte)  
0 0
Hallo,

die Bewegung des Kopfes + Überprüfen des Zeichens + Schreiben eines neuen Zeichens sind also insgesamt 2 Arbeitsschritte (bewegen+schreiben)?
Und ganz zu Anfang sitzt der Lesekopf schon über dem linkesten Zeichen der Bandinschrift?

Wäre auch als Alternativlösung denkbar, zuerst nach ganz rechts zu wandern, das letzte Zeichen zu überprüfen und zu Speichen (je ein Zustand für "es ist ein a" bzw "b"), und dann nach ganz links zu wandern und das entsprechende Zeichen vor die Bandinschrift zu setzen?

Vielen Dank und liebe Grüße!
...