Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität 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

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

Tue, 16 Mar 2021 11:29:34 +0000

Hallo Martin,

okay super :)

Vielen Dank für die schnelle Antwort!!

LG

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)

Kommentiert: Komplement von z.Bsp. 0000

Mon, 03 Feb 2020 14:52:36 +0000

Da hast du Recht, in diesem Fall würde sich durch die Änderung kein Fehler ergeben
Liebe Grüße,
Nico (Tutor)

Antwort bearbeitet: Konfigurationsabfolge Turingmaschinen

Mon, 03 Feb 2020 11:49:45 +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)

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

Sun, 05 Jan 2020 14:55:08 +0000

Super, ja es ist leider etwas unübersichtlich.

Vielen Dank schönen Feiertag (;

Roman

Antwort ausgewählt: Leeres Wort bei Turing-Maschinen

Sun, 06 Jan 2019 16:32:09 +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.

Kommentiert: Frage zu A73, Übungsbuch Turingmaschine

Sun, 07 Jan 2018 15:59:09 +0000

Genau. s0 sorgt dafür, dass der Lese-/Schreibkopf auf dem Zeichen ganz rechts steht. Die anderen beiden Zustände wird nun die geforderte Umwandlung der Bandinschrift in ihr Zweierkomplement vorgenommen und auf dem linkesten Zeichen des konvertierten Wortes stehengeblieben.

Schönen Abend noch!

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.

Antwort ausgewählt: Alternativlösung

Thu, 02 Feb 2017 14:26:39 +0000

Hallo,

ja, Ihre Lösung ist auch korrekt.

Kommentiert: 2er-Komplement von 000?

Thu, 26 Jan 2017 18:24:18 +0000

Wie schon in der alten Antwort geschrieben, ist die Aufgabenstellung vielleicht nicht genau genug, aber ein Fehler ist es nicht. Man könnte alternativ statt des Sterns auch eine Eins beim Lesen von $\star$ in $s_2$ schreiben, weil nicht spezifiziert wurde, was im Fall eines Überlaufs passiert.

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

Wed, 25 Jan 2017 12:58:15 +0000

Allerdings kann es bei Komplexitätsbetrachtungen sinnvoll sein, wenigstens zu fordern, dass eine Turingmaschine jedes Zeichen der Eingabe mindestens einmal "gesehen" hat - dass also (definitionsgemäß) keine Turingmaschine existieren darf, die weniger als lineare Zeit für die Bearbeitung ihrer Eingabe benötigt. Das hat aber eher technische Gründe - und das müssen Sie in diesen Details für Info 2 nicht wissen.

Kommentiert: Allgemeine Frage

Wed, 11 Jan 2017 14:02:51 +0000

In den Altklausuren war meines Wissens immer eine Kombination aus Turingtafel und einer Beschreibung, was die einzelnen Zeilen tun, verlangt.

Kommentiert: Verständnisfrage 2-Komplement

Fri, 22 Jul 2016 08:30:31 +0000

wird das erste Bit auch gekippt? Es handelt sich doch um das Vorzeichen Bit?
w'=2^(n-1)-w oder?

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)

Kommentiert: Alternativer Lösungsvorschlag

Tue, 09 Feb 2016 09:52:02 +0000

Ja so denke ich kann man die Turingmaschine auch beschreiben ;)

Beantwortet: Zustandsänderung

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

Hallo unegn,

siehe Kommentar!

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)

Erneut getaggt: Bildung 2er Komplement klausurrelevant?

Sun, 23 Nov 2014 11:22:49 +0000

muss man die bildung des 2er komplementes für die klausur draufhaben? ich habe davon in der vorlesung nichts mitbekommen.

danke & gruß

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: Alternative Vorgehensweise

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

Ja, das würde hier auch funktionieren.

Sven (Tutor)