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

0 Pluspunkte 0 Minuspunkte
159 Aufrufe

Ist folgende Überführungstabelle auch richtig?

Die TM überprüft also mit Sog und Sou, ob das Wort eine gerade Anzahl an Zeichen enthält.

Ist das nicht der Fall, geht die TM über in Sx, eine Senke, welche kein Endzustand ist.

Andernfalls geht die TM über Sz zurück zum ersten Zeichen, ersetzt dieses durch ein N oder ein E  und hängt hinten dementsprechend auch ein N oder E an das Wort an. Auf dem Rückweg in Szo wird die erste 0 oder 1 auch in ein N oder ein E umgewandelt, damit schließlich maximal das halbe Wort hinten angehängt wird. Danach wechselt die TM in Sz1, bis Sie wieder auf ein N oder E trifft, woraufhin die TM die Lese-/Schreibeinheit nach rechts bewegt und in Ss wechselt und wieder den selben Prozess durchläuft wie zuvor beschrieben.

Enthält das Wort nur noch Ns und Es wechselt die TM in SF und überschreibt alle Ns und Es mit einer 0 oder 1.

Über ein Feedback wäre ich sehr dankbar.

Viele Grüße

in TUR-AD von  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo.

Ich weiß nicht ob du die Aufgabe ganz verstanden hast. Ich erkläre nochmal ganz kurz, was die Turingmaschine A können soll.
Das Wort 11001101010101 ist w 1100110 ist u, 1010101 ist v. |u| ist 7 und |v| ist auch 7. w hat also eine gerade Anzahl an Zeichen. Nun soll das Wort u nochmal hinten an uv geschrieben werden. Das Wort was rauskommen soll ist also 110011010101011100110. Das ist eine sehr komplexe Turingmaschine, wie du in der Lösung auch siehst. Deine Turingmaschine hat deutlich zu wenig Zustände um eine richtige Alternativlösung zu sein.

Außerdem ist deine Turingmaschine sehr schwer zu lesen.

Grüße, Felix(Tutor)
von uwdtl uwdtl Tutor(in) (103k Punkte)  
0 0
"Deine Turingmaschine hat deutlich zu wenig Zustände um eine richtige Alternativlösung zu sein. "
Was für eine Schande von einem Info-Tutoren so eine Aussage zu hören. In der Informatik werden gerade kurze und elegante Ansätze gesucht. Die angegebene Turingmaschine akzeptiert meiner Meinung nach genau die in der Aufgabenstellung angegebenen Wörter und ist außerdem um einiges kompakter als die der Musterlösung.  Ich denke Felix, du solltest dir die Überführungstabelle noch einmal genauer anschauen und ein fundiertes Argument dafür liefern, dass sie nicht korrekt ist!
salam alaikum
0 0
Hallo usdqz.
Du hast Recht, ich war wohl etwas zu sehr geprägt von der Lösung, dass ich mir nicht vorstellen konnte, dass diese Lösung richtig sei.
Bei der Erklärung hat mich das maximal so verwirrt, dass ich mir sicher war, der Student (hast du sie geschrieben usdqz?) hätte die Aufgabe nicht richtig verstanden.

Mit modernster Kamera und Entschlüsselungstechniken ist es mir mittlerweile gelungen alles auf dem Foto zu erkennen und ich muss zugeben:
Ich bin begeistert! Die Lösung funktioniert (Ich bin mir nicht ganz sicher, weil ich manche Zeichen wirklich nicht erkennen kann, aber der Ansatz ist klug und richtig!) und gibt genau die richtige Lösung. Die Übungsleiter werden begeistert sein von dieser schönen, eleganten und kurzen Lösung.  

Ich lasse meine erste Antwort nochmal stehen um an diese Schande zu erinnern!

Grüße, Felix(wahrscheinlich bald kein Tutor mehr, weil gefeuert)
...