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 endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
217 Aufrufe
Hallo,

leider fehlt mir der Ansatz wie man Turingmaschinen angeben kann.
Die Aufgabe 5, Übungsblatt 3, kann ich beispielsweise nicht nachvollziehen. Die Übergänge sind mir nicht klar.

Haben Sie einen Tipp, wie man allgemein bei solchen Aufgaben vorgeht?

Vielen Dank!
in HU-3-2 von uhevq uhevq Lernwillige(r) (160 Punkte)  
Kategorie geändert von

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

Also vorneweg, die Aufgabe HU-3-2 (das ist Aufgabe 5 vom 3. Übungsblatt - Sie sollten möglichst im Forum immer die ID benutzen) gehört zu den allerschwersten Aufgaben, die wir überhaupt in den Übungen stellen. Vor allem vom Umfang her geht das auch weit über das hinaus, was wir in einer Klausur fragen würden! (Sowohl der a)-Teil als auch noch mehr der b)-Teil.) Die Konzepte, die dort verwendet werden, etwa der Binärzähler, sollten Sie aber von der Idee her schon verstanden haben. (Wobei auch der b)-Teil etwas einfacher ohne Binärzähler implementiert werden könnte.)

Ein Tipp bei Aufgaben, wo die Lösung bekannt ist und Sie sie nicht verstehen, ist natürlich, die Übergänge im XWIzard nachzuvollziehen. In diesem Fall wäre das für den b)-Teil dieser Link. Das sieht zunächst etwas unübersichtlich aus, aber beim zweiten Hinsehen erkennt man schnell die unterschiedlichen Programmbereiche, wie sie auch weiter unten in der Lösung erklärt und auch graphisch dargestellt sind. Auf diese Weise versteht man - mit etwas Anstrengung - sehr gut, wie die einzelnen Zustandsübergänge wirken und zu den gewünschten Abläufen entlang dieser Programmbereiche führen. (Am besten laden Sie die PDF herunter, dann können Sie leichter hineinzoomen.)

In diese Richtung geht auch mein zweiter Tipp: Sie sollten sich die Übergangstabelle einer Turingmaschine immer als ein Programm vorstellen. (Im Lehrbuch sprechen wir auch vom "Turingmaschinenprogramm".) Wenn man etwas Übung hat, unterscheidet sich das Programmieren einer Turingmaschine nicht so sehr vom Schreiben eines Java-Programms (oder eines Programms in einer anderen gängigen Programmiersprache). Sie sollten sich zunächst überlegen, welche unterschiedlichen Teilaufgaben das Programm lösen soll und diese dann nacheinander in Zustandsübergänge umsetzen. Wenn wir den einfacheren a)-Teil der von Ihnen angesprochenen Aufgabe betrachten, kann man sagen, dass es drei relativ abgetrennte Bereiche gibt:

  1. Prüfen, ob "das aktuelle" Zeichen in der vorderen Hälfte dasselbe ist wie das entsprechende Zeichen in der hinteren Hälfte.
  2. Das "aktuelle" Zeichen wird dabei durch die Position des rechtesten bisher geschriebenen $K$ bezeichnet. Daher muss während des Prüfens jeweis das abgearbeitete Zeichen vorne und hinten durch $K$ überschrieben werden.
  3. Falls die vordere Hälfte abegearbeitet ist, also keine Nicht-$K$-Zeichen mehr enthält, prüfen, ob auch die hintere Hälfte keine weiteren Zeichen enthält (also wirklich eine "Hälfte" ist und nicht länger).

Diese drei Bereiche müssen durch Turingmaschinenübergänge umgesetzt werden, was aber relativ einfach möglich ist. Einen guten Blick zu entwickeln, welche Aktionen eine Turingmaschine leicht ausführen kann und wie diese Aktionen zu einem bestimmten Zweck eingesetzt werden können, ist der Knackpunkt, und das geht letztendlich nur mit Übung. Die drei gerade beschriebenen Bereiche sind aber ganz typisch und werden in der einen oder anderen Form in vielen unserer Aufgaben verwendet.

Ich würde vorschlagen, Sie versuchen, mit meiner Erklärung das Programm etwas besser zu durchschauen und melden sich nochmal, wenn Sie weiterhin Probleme haben.

von Dozent (10.1m Punkte)  
Bearbeitet von
0 0
Vielen Dank!
Ist es ausreichend die Zustandsänderungen, wie beim XWizard, hinzuschreiben oder wird die Tabelle auf dem Lösungsblatt verlangt?
0 0
Das können Sie machen, wie Sie wollen, beides geht und beides werten wir gleich. Manchmal geben wir in der Klausur allerdings eine Turingtafel vor, und dann bietet es sich natürlich an, diese zu nutzen.
...