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 1 Minuspunkt
37 Aufrufe
da ich nicht verstehe, weshalb das # benötigt wird, habe ich wohl nicht verstanden, was die Sprache eigentlich vorschreibt und weshalb das  nötig ist. Könnte mir bitte jemand auf die Sprünge helfen? Vielen Dank.
in HU-3-2 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

Die Wörter der Sprache haben die Form x$x, d.h. es kommt zweimal hintereinander die selbe Folge von 0 und 1. Diese beiden Teile sind durch ein $ getrennt, also z. B. 01101$01101

Die Idee der TM in der Lösung ist, das erste Zeichen des linken Teils zu lesen, im Zustand zu speichern und dann nach rechts bis hinter das $ zu spulen. Dann wird das Zeichen rechts neben dem $ mit dem im Zustand gespeicherten verglichen. Unterschiedliches Zeichen -> TM bricht ab, Wort nicht akzeptieren. Wenn das Zeichen gleich ist, dann nach links spulen auf das zweite Zeichen der Eingabe und dieses mit dem zweiten Zeichen des rechten Teils vergleichen (auf die gleiche Weise) usw. Das Problem ist nun, dass x beliebig lang sein kann, man muss daher markieren, welche Zeichen man bereits verglichen hat, um das nächste unverglichene Zeichen bzw. die passende Stelle im rechten Teil  zu finden. Eine einfache Möglichkeit ist, alle Zeichen, die man bereits verarbeitet hat, mit # zu überschreiben. Dann kann man das nächste zu verarbeitende Zeichen leicht finden (das Zeichen rechts von #)

Gruß,

Tobias (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...