Hi,

kann es sein dass in der Folie zur Turingmaschine ein Tippfehler ist?
Und zwar bei Definition 17.1:
Soll die Menge Z hier eigentlich Q sein?

Ansonsten meine Frage dazu: Was ist Z? Eine Definition habe ich nicht gefunden.


Dann gleich noch eine Frage:
Was ist das Eingabealphabet? Die Menge der möglichen Zeichen die von der Turingmaschine aufs Band geschrieben werden? Also eine Teilmenge des Bandalphabets (Edit: ne, kann ja gerade nicht sein, steht ja auf der Folie)?

Soll die Menge Z hier eigentlich Q sein?

Ja.

Dann gleich noch eine Frage:
Was ist das Eingabealphabet? Die Menge der möglichen Zeichen die von der Turingmaschine aufs Band geschrieben werden? Also eine Teilmenge des Bandalphabets (Edit: ne, kann ja gerade nicht sein, steht ja auf der Folie)?

Das Eingabealphabet ist die Menge der Zeichen, die am Anfang der Rechnung auf dem Band stehen duerfen, also eine Teilmenge des Bandalphabets. Das Zeichen auf der Folie bedeutet "echte Teilmenge" (das # ist nach Definition immer Element des Band-, aber nicht des Eingabealphabets)

Danke!

Ist es möglich, dass in der Aufgabe 9.3 in der Formulierung der DTM das Symbol für das unbeschriebene Feld fehlt?

Wenn ja, dann müsste es wohl so aussehen:

[img]http://mokrates.de/cgi-bin/texstring?M%20%3D%20(%5Cleft%5C%7Bq_%7B0%7D%2Cq_%7B1%7D%2Cq_%7B2%7D%5Cright%5C%7D%2C%5Cleft%5C%7B0%2C1%5Cright%5C%7D%2C%5Cleft%5C%7B0%2C1%2CRAUTE%20%5Cright%5C%7D%2C%5Cdelta%2Cq_%7B0%7D%2CRAUTE%2C%5Cleft%5C%7Bq_%7B2%7D%5Cright%5C%7D)[/img]

RAUTE soll da natürlich # sein, aber \# hat der Editor leider nicht akzeptiert.

Ist es möglich, dass in der Aufgabe 9.3 in der Formulierung der DTM das Symbol für das unbeschriebene Feld fehlt?

Sehe ich auch so. Aber da besagtes Symbol aus (Speicherbandalphabet ohne Eingabealphabet) stammen soll und jene Menge nur ein Element enthält (nämlich die Raute), ist das sowieso eindeutig. Vielleicht darf man das dann sogar weglassen, wer weiß.

Jo, daran habe ich auch erst gedacht, aber was einmal ein 7-Tupel ist, das sollte auch eins bleiben :-)

Zur akzeptierten Sprache: Die gegebene TM mit der Überführungsfunktion der ersten Teilaufgabe akzeptiert ja nur Wörter, die aus einer beliebig langen Folge von 01 bestehen (da sie ja sonst nicht in den Endzustand gelangt) - wie schreibt man das auf? Oder ist mein Standpunkt schon falsch?

Dein Standpunkt ist nicht ganz richtig. Mit 01 bist Du wieder beim Zustand q_0. Aber aufschreiben würdest Du es als [img]http://mokrates.de/cgi-bin/texstring?%5C%7B01%5C%7D%5E%7B%5Cast%7D[/img], das ist die Menge aller Zeichenketten mit beliebig oft wiederholten 01 inklusive des leeren Wortes - also back to the roots of FGI-1 [img]http://www.fb18.de/gfx/23.gif[/img] (für die richtige Antwort wirst Du auch noch die Konkatenation brauchen - gutes Stichwort, falls Du nochmal was nachschlagen musst. Hat einen Kringel als Symbol.)

/edit: Schlecht zu erkennen, das geLaTeXte soll "{01} hoch Sternchen" sein.

Äh ja klar, mein Fehler - ich meinte ne beliebig lange Folge von 01 mit ner anschließenden 0.

L(M) = {{01}* o {0}}
ist formal bestimmt nicht korrekt ausgedrückt, oder?
das "o" soll hier mal das Zeichen der Konkatenation darstellen.

Was fragst Du denn so pessimistisch. Ist fast richtig. Jetzt hast Du allerdings eine einelementige Menge von Mengen. Du brauchst aber nur eine Menge.
Einfacher gesagt - lass die äußeren Mengenklammern weg. [img]http://www.fb18.de/gfx/22.gif[/img]

Hast du L(M) irgendwo gefunden (wo? würde mich interessieren, wenn's dazu 'ne standardisierte Benamung gibt) oder Dir ausgedacht?

Ich denke mal, das ist bezogen auf den neuesten Skriptteil (Folie 15), Definition 18.16 - da ist das für eine NTM definiert.

Was mich noch interessieren würde: Die Funktion der zweiten Teilaufgabe lässt ja zu, dass man auf zwei Arten in den Endzustand gelangt.
Die erste kommt dann auch zum Stillstand, die andere bewegt den Kopf noch einmal. Für eine akzeptierte Sprache ist aber nur gefordert, dass man mittels der Wörter irgendwann zum Endzustand kommt, oder?