Da es ja schon Tradition ist eröffne ich mal einen Thread zum 13. und damit letzten Blatt. Ich finde es unheimlich unzugänglich, aber das ist ja meine Sache. Konkret hätte ich einpaar Fragen.
"Sei L13.2 eine beliebige Typ-1 Sprache. Zeigen Sie, dass die Menge
Lrev
13.2 := {wrev | w ∈ L13.2}
der Spiegelwörter einer kontextsensitiven Sprache von einer Turingmaschine mit linearem
Platzbedarf akzeptiert werden kann!"
Ist das gezeigt, wenn ich eine Turingmaschine angebe?
Zweiter Frage: 13.1
δ(q0, 0) := (#, r, q0); Das ist eine Übergangsfunktion einer Turingmaschine (natürlich noch nicht vollständig). Diese Schreibweise gibt mir irgendwie Rätsel auf. Wie bröckelt man sich das auf?
Man ist in Zustand q0 und bekommt eine 0 eingelesen (δ(q0, 0)), soweit bin ich mir sicher. Das # macht mir Probleme, was bedeutet es hier? Heisst der "zweite Teil" : nach dem Einlesen der 0 schreibe ich # aufs Band, Band fährt nach rechts und man bleibt im Zustand q0?
"Sei L13.2 eine beliebige Typ-1 Sprache. Zeigen Sie, dass die Menge
Lrev
13.2 := {wrev | w ∈ L13.2}
der Spiegelwörter einer kontextsensitiven Sprache von einer Turingmaschine mit linearem
Platzbedarf akzeptiert werden kann!"
Ist das gezeigt, wenn ich eine Turingmaschine angebe?
Eine TM, von der Du zeigst, dass sie mit linearem Platz auskommt. Wobei dann noch das _klitzekleine_ Problem bleibt, dass L13.2 nicht konkret gegeben ist, aber das ist ja nicht wirklich ein Problem, oder?
Zweiter Frage: 13.1
δ(q0, 0) := (#, r, q0); Das ist eine Übergangsfunktion einer Turingmaschine (natürlich noch nicht vollständig). Diese Schreibweise gibt mir irgendwie Rätsel auf. Wie bröckelt man sich das auf?
Man ist in Zustand q0 und bekommt eine 0 eingelesen (δ(q0, 0)), soweit bin ich mir sicher. Das # macht mir Probleme, was bedeutet es hier? Heisst der "zweite Teil" : nach dem Einlesen der 0 schreibe ich # aufs Band, Band fährt nach rechts und man bleibt im Zustand q0?
Genau.
Dankeschön!
Eine TM, von der Du zeigst, dass sie mit linearem Platz auskommt. Wobei dann noch das _klitzekleine_ Problem bleibt, dass L13.2 nicht konkret gegeben ist, aber das ist ja nicht wirklich ein Problem, oder?
Wie "zeige" ich das? Alles, was mir einfällt ist eine "logische Begründung" (informal).
Dass die Sprache nicht angegeben ist habe ich nichtmal als Problem erkannt. Ist das nicht vollkommen egal wie die Sprache ist? Ich brauche ja nur zu wissen, dass sie da ist und dass ich das, was da ist einfach umdrehen muss. Welche Zeichen genau ich umschreiben muss interessiert den Prozess ja wenig.
In der Bonusaufgabe 13.3 steht, ein falsches Kreuz erzielt -1 Punkt. Bedeutet das, dass ich mir mit der Bonusaufgabe Minuspunkte einhandeln kann? o_O
Was soll das denn?
Ich denke der Wertebereich ist [latex]\mathbb{N}[/latex] (also keine negativen Punkte, Minimum ist Null)
hi leute,
akzeptiert die DTM aus Aufgabe 13.1 mit leerem Band? Oder ist etwa q2 der Endzustand?
Danke,
Arthur
woran sieht man das? ich sehe keinerlei anzeichen dafür, dass q2 der endzustand sein soll. (ebenso dass q0 der Startzustand sein soll)
gruß,
arthur
woran sieht man das? ich sehe keinerlei anzeichen dafür, dass q2 der endzustand sein soll. (ebenso dass q0 der Startzustand sein soll)
DTM T13.1 := (Q,Σ, Γ, δ, q0,#, {q2}):
Schau dir das doch nochmal ganz genau an. Kommt da q0 und q2 drin vor?
Merk dir die Stellen, an denen sie kommen und schau nochmal im Skript oder Wiki nach, wofür die einzelnen Stellen des 7-Tupels stehen. (wiki:
http://de.wikipedia.org/wiki/Turingmaschine)
woran sieht man das? ich sehe keinerlei anzeichen dafür, dass q2 der endzustand sein soll. (ebenso dass q0 der Startzustand sein soll)
DTM T13.1 := (Q,Σ, Γ, δ, q0,#, {q2}):
Schau dir das doch nochmal ganz genau an. Kommt da q0 und q2 drin vor?
Merk dir die Stellen, an denen sie kommen und schau nochmal im Skript oder Wiki nach, wofür die einzelnen Stellen des 7-Tupels stehen. (wiki:http://de.wikipedia.org/wiki/Turingmaschine)
Da haben wir aber Glück gehabt, dass die Schreibweise in Wikipedia sich mit der von der FGI-1 Präsentation deckt! Das muss nicht immer so sein, und könnte (gerade bei Wikipedia) übermorgen schon wieder anders lauten!
Wikipedia ist KEINE in wissenschaftlichen Arbeiten zitierfähige Quelle (auch besser nicht in Seminararbeiten oder Bachelorarbeiten), Bücher und Zeitschriftenartikel wissenschaftlicher Reihen dagegen schon!!
naja. Scheinbar gibt es 2 Versionen des Aufgabenblattes. Und meine Frage war auf die alte bezogen… wo keinerlei Definition der TM angegeben war… lediglich die Zustandsübergänge.
gruß,
Arthur
Da haben wir aber Glück gehabt, dass die Schreibweise in Wikipedia sich mit der von der FGI-1 Präsentation deckt! Das muss nicht immer so sein, und könnte (gerade bei Wikipedia) übermorgen schon wieder anders lauten!
Wikipedia ist KEINE in wissenschaftlichen Arbeiten zitierfähige Quelle (auch besser nicht in Seminararbeiten oder Bachelorarbeiten), Bücher und Zeitschriftenartikel wissenschaftlicher Reihen dagegen schon!!
Schon richtig, aber ich hab ja vorher bei Wiki geguckt und gesehen, dass sie "halbwegs brauchbar" ist. Dort ist es einfach sehr schön aufgelistet finde ich.
Und wissenschaftliche hin oder her, ich glaube man kann jeden einzelnen Studenten in Hamburg befragen und jeder wird sich Hilfe bei Wikipedia gesucht und gefunden haben, weil der wissenschaftliche Brei des Profs manchmal einfach nicht sehr einleuchtend ist/erklärt wird.
Die Frage hatte ich auch in der übung gestellt, als ich geschaut hatte war auch noch kein Endzustand angegeben und dann wurde natürlich erstmal erklärt wie man das Tupel liest … ;)
