Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-3-2

Beantwortet: Turingmaschine

Fri, 21 Jan 2022 17:18:29 +0000

Hallo,

hier gehört zum Beispiel das Wort 101S101 oder 00S00 dazu, also links und rechts vom S steht das gleiche Wort.

Man arbeitet das Wort dann Stück für Stück ab, man schaut sich das linkeste nicht abgearbeitete Zeichen an in der linken Hälfte und prüft dann, ob das Zeichen in der rechten Hälfte das gleiche Zeichen ist. Die abgearbeiteten Zeichen werden hier mit K überschrieben

Ein gute Vorgehen ist hier immer, ein Beispiel Wort zu nehmen und dann zu schauen, wie man Vorgehen kann.

Viele Grüße

Anne (Tutorin)

Beantwortet: Richtung in die ich gehe

Fri, 05 Jan 2018 16:53:33 +0000

Hallo,

selbstverständlich wäre dieser Ansatz auch korrekt, er würde lediglich mehrere Berechnungsschritte brauchen.

LG Tutor

Warum ist bei TM1 s2 kein endzustand ?

Thu, 04 Jan 2018 19:49:29 +0000

Warum ist s2 kein Endzusstand ?

hat sich geklärt!

Beantwortet: Verständins * auf Arbeitsband

Fri, 27 Jan 2017 10:14:50 +0000

Der steht dort bereits. Stellen Sie sich den Stern als ein ganz normales Bandzeichen vor. Zu Beginn ist das ganze Band von "links unendlich" bis "rechts unendlich" voll mit Sternen, bis auf einen kleinen Bereich in der "Mitte", wo die Eingabe steht. Die mit Stern beschriebenen Felder sind also nur in dem Sinn leer, dass dort ZU BEGINN kein Zeichen der Eingabe steht. Aber sobald die Turingmaschine losläuft, werden Sterne nicht anders behandelt als die übrigen Bandzeichen*, und wenn Sie wollen, können Sie dem Stern auch eine Bedeutung während der Rechnung oder sogar bei der Ausgabe am Ende geben.

* Bis auf die Spezialbehandlung beim Definieren der Bandinschrift: Sterne sind nur dann Teil der Bandinschrift, wenn sie nicht "ganz außerhalb" stehen, also sowohl rechts als auch links von ihnen noch Nicht-Stern-Zeichen oder der Lese-/Schreibkopf stehen. (Sonst wäre die Bandinschrift unendlich lang.)

Beantwortet: HU-3-2b Fehler in Turingtafel?

Tue, 03 Jan 2017 15:57:37 +0000

Ich kann Ihre Argumentation gerade nicht nachvollziehen (vielleicht bin ich auch nur unkonzentriert), aber das könnte daran liegen, dass ich selbst vor einigen Wochen noch ein paar kleine Fehler in der Aufgabe entdeckt und behoben habe. Das war leider, nachdem die Aufgabe schon ausgegeben worden war. Schauen Sie mal bitte, ob in der aktuellen Version der vermeintliche Fehler noch vorhanden ist oder nicht: Neue Version. (Eventuell müssen Sie die PDF im Browser aktualisieren durch drücken von F5, weil sonst die alte Version aus dem Cache geladen wird.)

Ich habe inzwischen auch einen Link zum XWizard eingefügt: http://www.xwizard.de:8080/Wizz?template=ID-C19279

Dort wird die Abarbeitung eines etwas einfacheren Wortes ($0101$) gezeigt, und das funktioniert jedenfalls.

Beantwortet: Verständnis

Sun, 07 Feb 2016 18:51:43 +0000

Hallo,

du kannst dann eine Turingmaschine schreiben die die komplette Bandinschrift um 1 Stelle nach rechts rückt, weil niemand hat etwas davon gesagt dass man nicht über den rechten Rand rausschreiben darf ;)

Viele Grüße,

Marc (Tutor)

Beantwortet: b): alternativer Lösungsvorschlag korrekt?

Mon, 21 Sep 2015 08:41:50 +0000

Ja, deine Idee, zuerst nach rechts druchzulaufen, und auch deine Lösung für die Überführungsfunktion sind korrekt!

Gruß, Janine (Tutorin)

Beantwortet: Warum sind A&E Elemente von B ?

Mon, 21 Sep 2015 08:40:15 +0000

Hallo,

das Eingabealphabet ist Grundlage für die Eingabe, also das, was zu Beginn auf dem Band steht.

Das Bandalphabet enthält alle Zeichen, die während der Rechnung auf das Band geschrieben werden können. Üblicherweise gehören dazu auf jeden Fall die Zeichen aus dem Eingabealphabet, und dann noch mindestens ein weiteres Zeichen, der *. Es können aber auch noch beliebige weitere Zeichen darin definiert werden (E und A sind aus unserer Sicht übrigens als Bandzeichen eigentlich nicht gut gewählt, weil E ja auch für das Eingabealphabet steht - aber das ist nicht Ihr Problem).

Viele Grüße

Lukas König

Beantwortet: unzureichende Definition der Überführungsfunktionen?

Mon, 21 Sep 2015 08:38:35 +0000

Du hast dich vermute ich verlesen. Beide TM sind so konstruiert, dass der Lesekopf komplett nach links wandert. Die Vorschriften sind jeweils (s0,0) --> (s0,0,L).

Man bleibt also im Zustand 0, bis man das Ende des Bandes erreicht hat.

Max (Tutor)

Beantwortet: Klausur: Wie müssen Überführungen angegeben werden?

Mon, 21 Sep 2015 08:36:49 +0000

Hallo,

bei Turingmaschinen ist die übliche Art, die Überführungsfunktion anzugeben, die Zustandstafel. Ich kann mir kaum vorstellen, dass Sie im Tutorium bei Turingmaschienen die einzelnen Übergänge "mit Pfeilen" angegeben haben - verwechseln Sie das nicht mit Kellerautomaten? Wir bitten Sie jedenfalls, in der Klausur bei Turingmaschinen immer eine Zustandstafel anzugeben. Die ist viel übersichtlicher und auch für Sie schneller auszufüllen.

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen und Micaela Wünsche

Beantwortet: Bewertungsschema in der Klausur: Regelung von Teilpunkten

Mon, 21 Sep 2015 08:35:35 +0000

Hallo,

gerade bei Turingmaschinen kann man so eine Aussage leider nicht treffen. Turingmaschinen zu korrigieren ist (vielleicht noch zusammen mit Kellerautomaten) eine der größten Herausforderungen für uns. Turingmaschinen sind wie Programmiersprachen, und Sie würden ja auch nicht fragen:

"Wenn ich in meinem Java-Programm 5 von 6 Zeilen richtig habe, bekomme ich dann 5/6 der Punkte?"

Das hängt halt sehr stark davon ab, was die anderen Übergänge / Zeilen machen und welcher der fehlerhafte ist und auch, was daran genau fehlerhaft ist.

Bei Turingmaschinen müssen wir uns in Sie hineinversetzen und versuchen nachzuvollziehen, was Sie implementieren wollten, und wo es dann u.U. gehakt hat. Wir schaffen das meistens ganz gut, aber trotzdem ist es auch ein guter Tipp, dass Sie, wenn Sie in die Einsicht kommen, sich die Korrektur der Turingmaschine bzw. des Kellerautomaten genauer anschauen. Wenn Sie uns schlüssig erklären können, was Sie sich gedacht haben und warum wir das nicht angemessen bepunktet haben, können Sie manchmal noch etwas herausholen.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Beantwortet: Wie kommt man auf die Anzahl der benötigten Zustände?

Mon, 21 Sep 2015 08:33:18 +0000

Hallo,

es gibt keine Formel o.ä. um die Anzahl der Zustände herauszufinden. Generell möchtest du in einem Zustand immer eine gewisse Information speichern (z.B. dass die Eingabe der a's beendet ist, und jetzt nur noch b's kommen dürfen oder ähnliches). Es gibt auch nicht nur DIE EINE korrekte Lösung, sondern verschiedene Lösungen können durchaus auch unterschiedlich viele Zustände haben! Wie viele Zustände du letztendlich brauchst, findest du erst beim Lösen der Aufgabe heraus. Übung macht den Meister ;-)

Viele Grüße

Lukas (Tutor)

Beantwortet: Vorgehensweise bei den Überführungsfunktionen?

Mon, 21 Sep 2015 08:31:54 +0000

Hallo,

schaue dir hierzu einfach mal die Folien aus dem Tutorium an. Dort ist das ziemlich anschaulich erklärt. Wenn du weitere Fragen hast, wäre es gut, wenn du diese ein bisschen konkretisieren könntest.

Viele Grüße

Lukas (Tutor)