Ich habe in der Vorlesung ja gesagt, daß nur bei leerer Eingabe der Lese/Schreibkopf unter einem Blank stehen darf. Wenn delta(q_0,B) dann z.B. in einen akzeptierenden Endzustand führt, dann hat die TM das leere Wort akzeptiert.
Nun geht’s ans Eingemachte, das im wesentlichen auf dem Unterschied zwischen Zeichen und Wort basiert: Für das leere Wort schreibt man „epsilon“. Das ist kein Zeichen der TM! Es ist also unmöglich, daß epsilon in Sigma oder Gamma enthalten ist. Dagegen kann, wie das Beispiel oben gerade gezeigt hat, epsilon in der als Sprache bezeichneten Menge L(M) der TM M sein! Diese Sprache ist nicht leer, man sagt also, daß die Sprache das leere Wort enthält, d.h. {epsilon} =/= {}! Da eine Gleichheit anzunehmen, ist ein ganz beliebter Fehler.
L(M) ={} ist aber natürlich auch möglich, z.B. wenn M sofort in eine Endlosschleife abrauscht.
Also zum Merken: Die leere Menge ist etwas anderes als die Menge, die das leere Wort enthält.
Ich habe in der delta-Tabelle nur solche Kombinationen von Eingaben eingetragen, die tatsächlich vorkommen können, dazu nen Kommentar. Denke, dass das genügen muss, die Tabelle hat eh schon genug Spalten.
Was am Ende von einem Ausführungsprozess auf dem Band steht, ist egal - wir müssen ja nur eine TM schreiben, die die Eingabe entscheidet.
Ja, die relevanten reichen, wenn Sie sagen, daß alle anderen delta-Werte undefiniert sind.
Über den finalen Bandinhalt haben wir im allgemeinen bei „Entscheiden“ ja (noch) nichts gesagt. Aber wie kommen Sie auf „kann man davon ausgehen“? Die TM macht nur das, was wir definiert haben, es läuft kein Betriebssystem im Hintergrund, das im Nachhinein noch Dinge auf dem Band erledigt, die Sie nicht programmiert haben.
Ja, die relevanten reichen, wenn Sie sagen, daß alle anderen delta-Werte undefiniert sind.[/quote]
Sehr gut, danke.
So meinte ich das auch nicht. Ich wollte eher wissen, ob die Eingabe während Band 1 beschrieben wird auch Band 2 bearbeitet und dieses mit Blanks auffüllt. Aber wenn ich so darüber nachdemke ist es für die Aufgabe wohl wirklich irrelevant.
