Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in TUR-AA

Beantwortet: Turingmachinen allgemein

Sat, 24 Jul 2021 07:01:36 +0000

Bei einer Turingmaschine stehen links und rechts vom Band unendlich viele * (Sterne/Leersymbole)

deterministische und nicht deterministische TM

Fri, 19 Mar 2021 11:31:18 +0000

Hallo,

was ist der unterschied zwischen einer deterministischen und nicht deterministischen Turingmaschine? Ich bin davon ausgegangen, dass beide die selbe Sprache akzeptieren.

viele Grüße

Beantwortet: HK 2018/19 Aufg.4 - Alternativlösung

Tue, 16 Mar 2021 11:25:44 +0000

Hallo uuiya,

auf den ersten Blick scheint deine Lösung auch richtig zu sein. Du hast sicherlich den intuitiveren Ansatz gewählt, brauchst dadurch eben auch einen Zustand mehr.

Was in der Musterlösung gemacht wird, ist einfach direkt beim ersten Durchlaufen des Bandes zu überschreiben. Wenn du beispielsweise als erstes eine 1 einliest, weißt du ja direkt, dass w ∉ L gilt. So spart man sich eben, die Funktionalität des Überschreibens separat zu regeln, wie es bei dir die Zustände S₄und S₅ machen :) Deine Lösung ist aber sicherlich leichter nachzuvollziehen, wenn jemand nur die Übergangstabelle hätte und versuchen würde zu verstehen, was die TM macht.

Beste Grüße,

Martin (Tutor)

Beantwortet: Turingmaschine endet, wo Lesekopf?

Sat, 08 Feb 2020 16:01:11 +0000

So lange es in der VL oder der Aufgabenstellung der Prüfung nicht anders steht, darf die TM stehen bleiben wo auch immer du willst...

(hauptsache sie bleibt stehen wenn sie ein Wort der gewünschten Sprache eingelesen hat und zwar nur dann)

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: Theoretische Informatik Übungsbuch A76

Thu, 06 Feb 2020 19:02:14 +0000

Wenn in der Aufgabe nichts explizit gegeben ist, ist es egal auf welcher Seite der Endzustand erreicht wird.

Gruß

Madita (Tutorin) (Alle Angaben ohne Gewähr)

Beantwortet: Turingmaschinen: mehr Zustände als in der Vorlagentabelle

Wed, 05 Feb 2020 13:18:06 +0000

In den letzten Jahren konnte man die Tabellen erweitern, solange es in der Aufgabenstellung nicht anders vorgegeben war... diese waren lediglich ein Anhaltspunkt.

Ihr solltet beim Üben aber darauf achten, dass euch die Tabellen reichen... je mehr Zustände, desto mehr Zeit benötigt ihr und die hat man in WiWi Klausuren bekanntlich selten im Überschuss.

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: Komplement von z.Bsp. 0000

Mon, 03 Feb 2020 13:01:29 +0000

0000 ist als Dezimalzahl eine Null.

Wie du hoffentliich weißt ist eine Null weder positiv noch negativ.

Das von links betrachtete erste Zeichen eines Zweier-Komplements dient lediglich der Klassifizierung als positiv/negativ.

Ob bei einer Null ein + oder - davor steht ist egal.

Somit ist 0000 als Zweier-Komplement Darstellung der Null (was die TM ausgibt) richtig.

Ändert man die Maschine nach deinem Vorschlag ergeben sich Fehler in anderen Fällen.

Grüße,

Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: Konfigurationsabfolge Turingmaschinen

Mon, 03 Feb 2020 09:39:40 +0000

DIe Tuppel in der Spalte Transition sind folgendermaßen aufgebaut: (Zustand in den man wechselt, Zeichen welches man schreibt, Bewegungsrichtung des Schreib-/Lesekopfes)

Die unter Konfiguration: (Zeichen links von Lese-/Schreibkopf, aktueller Zustand, Zeichen auf dem Lese-/Schreibkopf und die rechts davon)

Versuch nächstes mal selbst dahinter zu steigen, indem du dir die Aufgabe intesiv anschaust... dabei lernst du mehr.

Grüße,

Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: Turingmaschine letzte Position

Sat, 01 Feb 2020 15:20:13 +0000

Nein eine Touringmaschine muss nicht immer auf dem linkesten Zeichen stehen bleiben. Es sei denn es wird in der Aufgabenstellung explizit gefordert. Ist dies nicht der Fall, lasse deine Maschine einfach dort stehen, wo der Ablauf beendet wurde. Meiner Meinung nach ist Zeile s6 bei dieser Aufgabe deshalb nicht notwendig. In der Klausur würde so etwas deutlich angegeben werden. Grüße Hendrik (Tutor)

Beantwortet: Alternative Lösung Turingmaschine a^n b^n c^n (Vorlesung Bsp.)

Sat, 04 Jan 2020 15:52:32 +0000

Hallo uqysn,

leider liegt mir das Beispiel aus der Vorlesung aktuell nicht vor. Könntest du bitte zusätzlich noch die Aufgabenstellung und die Musterlösung schreiben? Dann schaue ich mir beide Lösungen gerne an.

Viele Grüße
Hannah (Tutorin)

Beantwortet: Leeres Wort bei Turing-Maschinen

Sun, 06 Jan 2019 16:18:34 +0000

Hallo ugmwm,

zu deiner ersten Frage:

Das leere Wort Lambda taucht nicht in deinem Eingabealphabet auf. Das war ja auch bei bspw. endlichen Automaten nicht der Fall, die das leere Wort akzeptieren sollten, und bei Turingmaschinen ist das genauso.

Zu deiner zweiten Frage:

Lambda taucht ebenfalls nicht in deiner Turingtafel auf. Wenn du eine Turingmaschine hast, die nur Wörter akzeptieren soll, die in der gegebenen Sprache enthalten sind, und das leere Wort da auch dazu gehört, dann entspricht die Codierung des leeren Wortes bei einer Turingmaschine dem Fall, dass einfach nur Sterne auf dem Band stehen. Nun gibt es zwei Möglichkeiten:

Die Konfiguration (s0, *) existiert nicht in der Turingtafel: Dann bleibt die Turingmaschine direkt „stecken“ und kann nichts weiterbearbeiten. s0 muss dann folglich ein Endzustand sein, um das leere Wort zu akzeptieren.
Die Konfiguration (s0, *) existiert in der Turingtafel: Dann muss es einen Berechnungspfad geben, der in einen Endzustand führt und damit das ursprünglich leere Wort (nur * auf dem Band) akzeptiert. Schau dir hierzu mal die Aufgabe 5 b) von Tut 3 an für den Fall, dass nur * (also das leere Wort) am Anfang auf dem Band stehen.

Ich hoffe ich konnte Dir damit helfen.

Viele Grüße

Claus (Tutor)

Beantwortet: Abgabeblatt Aufgabe Turingmaschine

Thu, 03 Jan 2019 16:11:28 +0000

Hallo ufuiu,

es ist nicht falsch, wenn du mehr Zustände benötigst und noch weitere Zeilen dazuzeichnest. (Aber eigentlich reichen die angegebenen Zeilen.)

Viele Grüße

Anne (Tutor)

Beantwortet: Annahme Turingmaschine zu Beginn über ganz linkem Zeichen

Tue, 23 Jan 2018 06:48:58 +0000

Die Kopfposition auf dem linkesten Zeichen der Eingabe ist Teil der Definition einer Turingmschine. Das müssen Sie nicht als Annahme formulieren, sondern Sie können (und müssen!) immer davon ausgehen, dass das so ist.

Ich möchte allgemein darauf hinweisen, dass Sie die Definitionen aus der Vorlesung genau lernen und verstehen sollten. Die vorgestellten Methoden funktionieren nur, wenn man nicht nur eine ungefähre Vorstellung von dem hat, was passiert, sondern wenn man in der Lage ist, in allen Situatioen (und das sind insbesondere auch die "Randsituationen", die nicht dem Regelfall entsprechen, sondern in Extremfällen auftreten) exakt nach Definition vorzugehen.

Wir prüfen in den Klausuren immer auch Ihr Wissen von diesen Randfällen ab.

Beantwortet: Frage zu A73, Übungsbuch Turingmaschine

Sun, 07 Jan 2018 12:43:01 +0000

Hey,

danke für die schnelle Antwort.

Auf Seite 27 steht z.B :"das R steht für der Lese/Schreibkopf bewegt sich eine Zelle nach rechts".

Was ich nicht ganz verstanden habe , ist was es bringt, wenn ich z.B, (s1,*,R) im Feld stehen habe - ich wechsel doch sowieso in den s1 Zustand- warum fährt die Turingmaschine dann nach rechts / Betrifft das dann den Folgezustand ?

Liebe Grüße und danke schonmal !

Beantwortet: Ratefähigkeit der nichtdeterministischen TM

Fri, 29 Sep 2017 10:08:39 +0000

Das zweite ist es, Sie können blind annehmen, dass, wenn es einen richtigen Weg, die Turingmaschine die richtige Abzweigung nimmt.

Beantwortet: Turingmaschine wo Lesekopf am ende?

Mon, 06 Feb 2017 15:32:44 +0000

Wenn nichts in der Aufgabe steht, können Sie den hinfahren, wo Sie wollen. Das ist für die Rechnung völlig unerheblich.

Beantwortet: Alternativlösung

Thu, 02 Feb 2017 11:36:18 +0000

Hallo,

ja, Ihre Lösung ist auch korrekt.

Beantwortet: TM als Akzeptor - Wort vollständig einlesen?

Wed, 25 Jan 2017 12:55:31 +0000

Eine Turingmaschine kann ja auf dem Wort hin und herspringen, es sogar verändern usw. Daher würde so eine Forderung keinen Sinn machen. Eine Turingmaschine akzeptiert also ein Wort, wenn sie in einem akzeptierenden Endzustand hält - ohne weitere Auflagen.

Beantwortet: Allgemeine Frage

Wed, 11 Jan 2017 12:44:05 +0000

Zur ersten Frage gilt ganz klar, dass Sie die Tabelle erweitern dürfen, wenn Sie das wollen. Wir würden aber nicht zu wenige Zeilen/Spalten für eine Minimalversion vorgeben - Sie DÜRFEN das also tun, aber nötig sein sollte es nicht. Sie müssen normalerweise nicht die Minimalversion angeben, sodass es auch mit so einer erweiterten Tabelle durchaus die volle Punktzahl geben kann.

Und was meinen Sie mit der "formalen Beschreibung"? Die ganze Definition einer Turingmaschine (mit Tabelle und allem) ist eine formale Beschreibung. Für Teile davon kann es auch Teilpunkte geben (allerdings nicht in der Bonusklausur, wo wir jede Aufgabe komplett als "richtig" oder "falsch" bewerten).

Beantwortet: Verständnis Mächtigkeit Turingmaschine

Sat, 13 Feb 2016 16:11:48 +0000

Hallo uydur,

damit ist gemeint, dass eine zu einer bestimmten Typ 0 Sprache zugehörige Turingmaschine jedes Wort in der Sprache akzeptiert, also 1 ausgibt. Umgekehrt kann es aber sein, dass die Turingmaschine für ein Wort, dass nicht Teil der Sprache ist nicht terminiert, also nicht zwangsläufig 0 ausgibt.

Viele Grüße

Gregor (Tutor)

Beantwortet: Verständnisfrage 2-Komplement

Wed, 10 Feb 2016 22:59:43 +0000

Hallo uidmb!

Meiner Meinung nach ist hier die Aufgabenstellung sehr unglücklich bzw. missverständlich formuliert. Mit w' ist meiner Meinung nach nicht die Zwei-Komplentdarstellung von w, sondern das Zwei-Komplement zu w gemeint.

Das Zwei-Komplement berechnet sich wie folgt (mit w und w' in der Formel als Dezimalzahlen interpretiert) :

w' = 2^n - w

Beispiel: Auf deinem Band steht w= 00111 (binär), das entspricht dem dezimalen Zahlenwert 7 (=1+2+4). Das Zweikomplement dazu erhälst du rechnerisch aus w' = 2^5 - 7 = 25, was binär der Zahl 11001 entspricht. Diese erzeugst du über das in der Musterlösung genannte Vorgehen, indem du zunächst alle Bits auf dem Band kippst (dann erhälst du 11000) und dann noch 1 dazuaddierst (so kommst du zum Endergebnis 11001, was gerade 25 ist (=1+8+16)).

Ich hoffe, das hilft dir weiter

Viele Grüße,
Janine (Tutorin)

Beantwortet: Zustandsänderung

Mon, 08 Feb 2016 12:27:23 +0000

Hallo unegn,

siehe Kommentar!

Beantwortet: Alternativer Lösungsvorschlag

Sun, 07 Feb 2016 21:39:57 +0000

Hallo,

das was nicht stimmt bei deiner Turingmaschine ist, dass du den Bitstring 0000 bspw. nicht verändern sollst, da 0000 beim zweierkomplement immer noch 0000 ist.

Deine Turingmaschine würde daraus ein 10000 machen, was nicht korrekt ist ;)

Viele Grüße,

Marc (Tutor)

Beantwortet: Formulierung der Aufgabe falsch?

Fri, 05 Feb 2016 17:11:54 +0000

Hallo,

spontan finde ich deine Idee der Aufgabenstellung sehr treffsicher.

Allerdings ist die Zweikomplement-Darstellung eben genau dazu da, "normale" Dualzahlen in ein entsprechendes Pendant umzuwandeln, welches dann als die negative Zahl interpretiert wird. Die Aufgabenstellung ist also schon passend.

Gruß

Max (Tutor)

Beantwortet: Interpretation der Fragestellung

Mon, 01 Feb 2016 17:02:10 +0000

Hallo,

zunächst einmal besteht die Bandinschrift nur aus 0 und 1, was im Prinzip schon ausreicht, um sie als Binärzahl zu interpretieren. Über ihr Vorzeichen o.Ä. ist nichts gesagt.

Ganz allgemein sind alle Darstellungen für negative Zahlen, wie sie beispielsweise in den Tutorien vorkamen, nur Möglichkeiten zur Codierung negativer Zahlen ausschließlich mit Nullen und Einsen. Sie beruhen also auf Konventionen.

Zur Umwandlung in das Zweierkomplement sind weiterhin zwei Schritte nötig:

1) Alle Bits kippen (0 zu 1 und andersrum)

2) An der niedrigsten Stelle eine 1 addieren

(Nur eine führende Null anfügen reicht nicht aus zur Umwandlung)

Ich hoffe, dass das Verständnisproblem bei der allgemeine Umwandlung damit klar wird und nehme an, dass sich damit auch die Lösung der Turingmaschine selbst ermitteln oder spätestens nachvollziehen lässt.

Gruß

Max (Tutor)

Beantwortet: Hilfe zu allternativem Lösungsvorschlag

Sun, 23 Nov 2014 12:38:02 +0000

Hallo,

ich erkenne dein Problem nicht. Das 2er-Komplement von 0000 ist 0000 (Überlauf wird bei 2er-Komplementbildung abgeschnitten). Das kann man sich auch daran vorstellen, dass 0 im 2er-Komplement kein Komplement hat (platzsparender Effekt dieser Darstellung).

Da alle 1en bei dir nach dem Kippen durch 0en ersetzt werden und du beim Stern stoppst (bzw. in s2 gehst, in dem nichts mehr passiert), sollte das so funktionieren.

Viele Grüße

Philippe (Tutor)

Beantwortet: Frage zur Definition des Automaten

Sun, 23 Nov 2014 12:36:16 +0000

Hallo,

E ist dein Eingabealphabet für dein Wort, dass am Anfang auf dem Band der Turingmaschine steht. Der Stern gehört zum Bandalphabet. Besteht also E aus 0 und 1, dann wird dein Wort am Anfang auch nur daraus bestehen. Später kannst du dieses ja mit beliebigen Zeichen überschreiben, so auch mit dem Sternchen.

Ich hoffe das hilft dir.

Grüße Jördis (Tutor)

Beantwortet: 2er-Komplement von 000?

Sun, 23 Nov 2014 11:23:12 +0000

Hallo Tanja,

meinen Sie bei den sich widersprechenden Posts diese beiden Aussagen:

> Im Gegensatz zum 1-Komplement-System hat die 0 im 2-Komplement-System nur eine Darstellung, nämlich 0000 (bei 4 Stellen, vgl VL 7-36).

und

> Du hast allerdings den Fall vergessen, wenn zum Beispiel das Eingabewort nur aus 0 besteht. also nehmen wir an die Bandinschrift ist "0000". durch das invertieren erhalten wir natürlich 1111. Wenn man nun aber noch die 1 addiert erhält man 10000, also ein Zeichen mehr auf dem Band. Das heißt du musst ganz links noch eine 1 anfügen. Also (s1, *) -> (se, 1, N)

Das Problem entsteht durch eine zu ungenaue Aufgabenstellung unsererseits, die man eigentlich verbessern müsste. Ich belasse es aber fürs erste bei dem Kommentar und denke nochmal darüber nach, wie man es besser formulieren könnte.

Der Punkt ist, das eine 2K-Darstellung immer auf eine bestimmte Bitzahl festgelegt ist. Wenn bei Rechenoperationen in der 2K-Darstellung Überläufe entstehen, werden die meist einfach ignoriert. Wir haben es also immer mit einer 2K-n-Kodierung zu tun, die jede Zahl mit genau n festen Bits kodiert. Eine Turingmaschine mit unendlichem Band könnte natürlich auch Überläufe berechnen und damit beliebig große Zahlen beherrschen, aber wie man das im 2-Komplement machen könnte, haben wir in der Vorlesung nicht behandelt.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Beantwortet: Frage zum 2er-Komplement

Sun, 23 Nov 2014 11:21:31 +0000

Hallo,

Im Gegensatz zum 1-Komplement-System hat die 0 im 2-Komplement-System nur eine Darstellung, nämlich 0000 (bei 4 Stellen, vgl VL 7-36).

Viele Grüße,

Vivian (Tutor)

Beantwortet: Alternativer Lösungsvorschlag

Sun, 23 Nov 2014 11:19:56 +0000

Ich denke deine Zustandstabelle ist fast richtig.

Du hast allerdings den Fall vergessen, wenn zum Beispiel das Eingabewort nur aus 0 besteht. also nehmen wir an die Bandinschrift ist "0000". durch das invertieren erhalten wir natürlich 1111. Wenn man nun aber noch die 1 addiert erhält man 10000, also ein Zeichen mehr auf dem Band. Das heißt du musst ganz links noch eine 1 anfügen. Also (s1, *) -> (se, 1, N)

Außerdem sollen wir ja am Ende über dem linkesten Zeichen stehen bleiben, das ist in deiner Lösung nicht berücksichtigt.

Grüße, Theresa (Tutorin)

Beantwortet: Beachtung leeres Wort?

Sun, 23 Nov 2014 11:18:53 +0000

Falls auf dem Band nur Sterne stehen, also keine Bandinschrift vorhanden ist, kommt die angegebene TM auch in den Endzustand.

Aber ich nehme mal an, dass man von einer sinnvollen Bandinschrift (d.h. ungleich lambda) ausgehen kann.

Sven (Tutor)

Beantwortet: Bildung 2er Komplement klausurrelevant?

Sun, 23 Nov 2014 11:17:53 +0000

Für die Bonusklausur nein, für die Hauptklausur ja (Kapitel 7).

Viele Grüße
Friederike Pfeiffer

Beantwortet: Alternative Vorgehensweise

Sun, 23 Nov 2014 11:16:47 +0000

Ja, das würde hier auch funktionieren.

Sven (Tutor)