Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 2
Ich wollt mal anfragen, nachdem ich das Blatt grad runtergeladen hab, was dieses # z.B. bei Aufgabe 8 bedeutet. (in der Vorlesung hatte er das letzten Freitag ja glaube ich auch, aber da war ich leider krank). Ist das einfach ein beliebiges Zeichen (außer 0 und 1) und ich geh dann auch damit wie mit einem normalen Zeichen um?
Ja, es handelt sich ganz einfach um ein weiteres Zeichen des Bandalphabets. Es wurde benutzt, um zwei Eingaben voneinander zu trennen (wenn man bloß 1er und 0er zur Verfügung hat, dann muss man sich irgendeine besondere Codierung ausdenken; so geht es einfacher).
danke für die schnelle antwort. Und noch allgemein zu TM muss ich da immer nur prüfen ob wirklich die Buchstaben aus der Menge genimmen werden, die bei L angegeben ist oder muss ich auch überprüfen, des ich hier bei der Aufgabe z.B. nicht ### habe?
Das musst du schon überprüfen, da # nunmal zu deinem Bandalphabet gehört und damit theoretisch beliebig in der Eingabe auftauchen kann. Die TM, die ihr konstruieren sollt, muss für jede beliebige Eingabe über dem Bandalphabet entscheiden, ob diese zur Sprache gehört oder nicht.
Das find ich aber komisch, da bei der AUfgabe 6 auch Eingaben der Form 0Y1 oder 01YY usw akzeptiert worden sind und nicht zu einem Fehler/Abbruch geführt haben… obwohl man ja auch nur 0 und 1 in der Sprache haben durfte…
Naja… du darfst wenn du willst gerne aus 00#00 im Zuge deiner Bearbeitung 0###0 machen, ist alles ok.
Nur wenn von Anfang an ein 0###0 auf dem Band steht, dann ist das ja kein Wort der Defintion der Sprache nach und sollte deswegen auch so behandelt werden.
Edit: Und akzeptiert wurden auch in Aufgabe 6 Eingaben wie 0Y1 nicht. Sie wurden nur auf dem Band… ich sag mal salop „toleriert“.
Aber wenn man Aufgabe 6 ausführt mit 0Y1 (ich habs gerade nochmal ausprobiert) würde man in den Zustand q5 kommen… Also warum sollte ich dann ### abhalten müssen?!?
Desweiteren bei Aufgabe 9 wenn ich ein Ä umschreib in AE, dann braucht das AE doch zwei Zellen und nicht eine wie das Ä oder soll AE in eine Zelle geschrieben werden?
Achtung, es gibt ein Eingabe- und ein Bandalphabet! Das Eingabealphabet ist eine Teilmenge des Bandalphabets. Du kannst dich drauf verlassen, dass wenn deine TM losläuft nur Zeichen aus dem Eingabealphabet auf dem Band stehen.
Hab das Übungsblatt jetzt nicht angeguckt, kann dir jetzt daher nicht sagen was darin gewünscht ist.
Die Eingabe besteht nur aus Elementen von Sigma.
AE (also als ein Zeichen) ist nicht Bestandteil des Alphabets, also kann es nicht in einer Zelle stehen (in einer Zelle steht zu jedem Zeitpunkt genau ein Zeichen aus dem Alphabet). Daher wird aus einer Zelle mit einem ‘Ä’ zwei Zellen mit ‘A’ und ‘E’.
ah ich verstehe 
dann macht das auch Sinn jetzt, dass man beachten muss, dass ### oder so als Eingabe auftreten kann Danke!!
Ja der Unterschied zwischen dem Band und dem Eingabealhabeth ist mir nicht so ganz klar: ist das Eingabealphabet, das was mein Wort enthalten darf und das Bandalpabeth alle Zeichen die meine Maschine überhaupt mächtig ist auf das Band zu schreiben? (Also andere Zeichen schafft sie nicht?)
ja genau. Bevor die Maschine startet ist nichts anderes als das Eingabealphabet (und blanks) auf dem Band, die Maschine kann dann beliebige Zeichen aus dem Bandalphabet lesen und schreiben.
danke echt noch mal für eure Hilfe 
Dann hab ich noch ne letzte Frage dazu: das leere Wort soll das dann immer akzeptiert werden oder nicht? Wenn das Leerzeichen selber nicht in Sigma steht. ABer das leere Wort ist doch in Sigma Stern trotzdem enthalten… aber solls akzeptiert werden weil in der Vorlesung hieß es doch, dass die Wörter immer aus Sigma Stern sind?
So langsam versteh ichs freu
Du musst aufpassen, dass du da nicht ein paar Dinge durcheinander bringst.
Das leere Wort (epsilon) ist aus Sigma (und eigentlich auch in jedem anderen Alphabet enthalten) und hat die Laenge 0. (quasi unsichtbar, wenn man so will 
)
Das Blank (Leerzeichen) hingegen hat die Laenge 1 und ist normalerweise nicht in Sigma enthalten.
Akzeptierend haelt die Maschine nur dann, wenn sie einen (akzeptierenden) Endzustand erreicht.
Bekommst du als Eingabe das leere Wort, dann stehen auf dem Band nur Blanks und die Maschine liest somit ein Blank.
Kannst du jetzt mit dem gelesenen Blank irgendwie in einen Endzustand gelangen, dann haelt die Maschine akzeptierend.
Kannst du allerdings keinen Endzustand erreichen, dann haelt deine Maschine nicht/nicht akzeptierend.
Hallo Leute,
eine Frage zum Verständnis zu Aufgabe 10. Ich versteh nicht so wirklich, worin die sich von der Aufgabe 8 (in Bezug auf die Lösung) unterscheidet. “Sprache aus Aufgabe 8 entscheidet”? Aufgabe 8 kann man doch mit einer relativ einfachen δ-Tabelle¹ lösen, ohne jegliche Ersetzungen und nur mit Bewegungen in eine einzige Richtung, oder unterschätze ich die Aufgabe? Welchen Vorteil sollte da eine 2-Band-Maschine bringen bzw. wie könnte sich das Programm unterscheiden?
Vielleicht kann mir ja jemand auf die Sprünge helfen…
Danke schonmal!
¹ plus natürlich die vollständige Beschreibung durch F, Q etc.
Die 2-Band Maschine hat eine deutlich bessere Laufzeit
Hast du dann auch darauf geachtet das bei
L = {w#w}
w = w gilt, oder muss das gar nicht so sein?
Klar ist das Wort vor dem #-Zeichen gleich dem Wort nach dem #-Zeichen. Auf einer 1-Band-TM ist das in bezug auf die Laufzeit deutlich schwerer nachzuprüfen als auf einer 2-Band-TM. Auf einer 1-Band-TM geht es auf gar keinen Fall (eine andere Redewendung für: es ist beweisbar unmöglich) in einem Durchgang über die Eingabe.
MfG
Rolf Wanka
Hallo allesamt,
ich hätte eine Frage zur Aufgabe 8 und 9 (oder eher im Allgemeinen zur TM):
Wie sieht es aus, wenn die Starteingabe lediglich aus Blanks besteht?
Das wäre ja dann die “Leere Menge” für die Turingmaschine und damit auch eine Teilmenge von L.
Muss ich diesen Fall auch verifizieren können oder wäre er automatisch wahr (oder denke ich gerade zu mathematisch und es existiert gar keine “Leere Menge” für die TM?)