Könnte mir jemand erklären, worin der Unterschied zwischen dem Bandalphabet GAMMA und dem Eingabealphabet SIGMA besteht? Irgendwie finde ich keine Stelle, an der das Eingabealphabet verwendet wird. Hat das irgendeine Funktion?
Das Bandalphabet enthält zum Beispiel das Zeichen # (Ende des Bandes oder wie auch immer) als spez. Sonderzeichen, da wäre es natürlich ungünstig, wenn dieses auch im Eingabealphabet zu finden wäre.
Könnte mir jemand erklären, worin der Unterschied zwischen dem Bandalphabet GAMMA und dem Eingabealphabet SIGMA besteht?
Ich habe das Skript noch nicht durch, aber für's erste soll das Bandalphabet ein Symbol für ein unbeschriebenes Feld enthalten., das natürlich nicht Teil des Eingabealphabet sein darf (Eingabe != beschrieben)
Irgendwie finde ich keine Stelle, an der das Eingabealphabet verwendet wird. Hat das irgendeine Funktion?
Also das Eingabealphabet enthält lediglich die Symbole, die "von außen" auf das Band geschrieben werden. Das Bandalphabet besteht hingegen aus alle Zeichen, welche die Turing-Maschine überhaupt verarbeiten kann. Also mindestens das Eingabealphabet und das "Leer"-Zeichen. Das (Eingabealphabet) ist wohl zumindest für die Definition von Berechenbarkeiten sinnvoll.
Ich kapier zwar noch nicht so ganz, wie etwas von "außen" aufs Band geschrieben werden soll, aber.. ich glaube mir dämmert so langsam, dass das "Nicht-Teilmenge-von"-Zeichen im Skript vielleicht ein "Doch!-Teilmenge-von"-Zeichen sein soll [img]
http://www.fb18.de/gfx/22.gif[/img]
LOL
das war durchaus ernst gemeint.
Das wird einfach definiert. Meinetwegen über eine Software. Die gibt dann als Startparamter mit "Auf Feld 1 steht ne 1, dann ne 3, …" auf den Weg. Der undefinierte Rest bleibt "#". Zumindest habe ich mir das immer so vorgestellt.
Hmm.. ich hoffe mal, das Wesentliche daran verstanden zu haben, aber…
Berndt, wenn du das hier liest: Frag mich das bitte nicht in der Prüfung! [img]
http://www.fb18.de/gfx/7.gif[/img]
Eingabealphabet = Ausgabealphabet
Im Bandalphabet (Gamma) können noch Hilfssymbols vorhanden sein, die weder ein- noch ausgegeben werden dürfen!
ich glaube mir dämmert so langsam, dass das "Nicht-Teilmenge-von"-Zeichen im Skript vielleicht ein "Doch!-Teilmenge-von"-Zeichen sein soll [img]http://www.fb18.de/gfx/22.gif[/img]
Das soll ein "echte Teilmenge von"-Zeichen sein (Kombination aus Teilmenge und Ungleich-Zeichen).
Das soll ein "echte Teilmenge von"-Zeichen sein (Kombination aus Teilmenge und Ungleich-Zeichen).
Das wurde aber gut verschleiert [img]
http://www.fb18.de/gfx/25.gif[/img]
Warum werden nicht einfach die Zeichen verwendet, die man auch in der Mathematik gebraucht?
[img]
http://www.cse.unsw.edu.au/~achim/Research/Philosophie/img57.gif[/img]
[img]
http://mo.mathematik.uni-stuttgart.de/notationen/notationen_mengenlehre/img9.png[/img]
Wenigstens weiß ich es jetzt [img]
http://www.fb18.de/gfx/23.gif[/img] Danke euch!
Ich kapier zwar noch nicht so ganz, wie etwas von "außen" aufs Band geschrieben werden soll, aber
Was bringt dir denn eine Turingmaschine, wenn du ihr keine Eingabe gibtst. Dann wäre auch eine Funktion zu modellieren etwas langweilig :) Die Turingmaschine startet im allgemienen ja in der Art q0w wobei q0 der Startzustand ist und w irgendwas als eingabe. Und da darf halt nur das Sigma (?) Also das EIngabealphabet benutzt werden [img]
http://www.fb18.de/gfx/28.gif[/img]
Zumindest in unserem F2 Skript werden die Symbole auf den ersten Seiten eingefuehrt…
Wer lesen kann…
SCNR
MoKrates
Die Turingmaschine startet im allgemienen ja in der Art q0w wobei q0 der Startzustand ist und w irgendwas als eingabe.
Also die Eingabe ist jetzt das, was auf dem Band steht und dann von der Turingmaschine gelesen und verarbeitet wird, ja?
anders gehts doch nicht, wie stellst du dir denn die
funktionsweise des dings vor (akzeptieren eines wortes)?,
oder darf das Berndt auch nicht fragen? ;)
eingabe steht auf dem band,
LSK über dem linkesten symbol der eingabe,
verarbeitung geschieht dann auch auf diesem band
(und in der endlichen kontrolle),
dessen inhalt beliebig verändert werden kann,
zum akzeptieren eines wortes einer sprache muss die TM
einfach nur in einem endzustand halten,
zum berechnen eines funktionswert zu einer eingabe muss sie
in einem endzustand halten,
und vorher den funktionswert (und nur das) auf das arbeitsband
schreiben und den LSK wieder über das linkeste symbol positionieren,
ist die funktion für eine eingabe nicht definiert oder
soll die TM ein wort nicht akzeptieren,
dann hält sie nicht
(grade heute wieder prüfungsfrage, also merken ;) )
Wozu braucht man dann Zeichen, die nicht im Eingabealphabet sind, nicht das # sind, aber trotzdem auf dem Band herumlungern?
dazu weiss ich immer noch nichts,
ausser aus schönheitsgründen..,
edit
es könnte natürlich eine funktion
von {a,b}* nach {c,d}* abbilden,
da wärs dumm mit der ausgabe, wenn man nur a,b, # hat ;)
Wozu braucht man dann Zeichen, die nicht im Eingabealphabet sind, nicht das # sind, aber trotzdem auf dem Band herumlungern?
Man könnte den internen Sputz damit verstecken. Angenommen du willst z.B. Funktionen N–>N berechnen und musst intern mit vielen weiteren Zeichen arbeiten. Dann braucht der Eingeber doch nicht sehen, was du alles machst. Sozusagen eine Sache des Interfaces. Slaters ansatz ist aber wahrscheinlich noch wichtiger [img]
http://www.fb18.de/gfx/28.gif[/img]
Wozu braucht man dann Zeichen, die nicht im Eingabealphabet sind, nicht das # sind, aber trotzdem auf dem Band herumlungern?
Wenn Du z.B. ein Zeichen a aus der Eingabe markieren möchtest, weil es bereits gelesen und einmal verarbeitet worden ist, es später aber nochmal verarbeiten musst, dann braucht Du im Bandalphabet ein weiteres Zeichen z.B. â. Dieses darf aber nicht im Eingabealphabet sein, sonst "weiß" die Turingmaschine ja nicht, ob es sich um ein markiertes a oder ein â aus der Eingabe handelt.
edit
es könnte natürlich eine funktion
von {a,b}* nach {c,d}* abbilden,
da wärs dumm mit der ausgabe, wenn man nur a,b, # hat ;)
Du kannst kein # ausgeben, da dieses Symbol ja für "unbeschriftet" steht, genau so wie das lambda bei den endlichen Automaten, und jenes ist, welches den für
alle Eingabealphabete entscheidenden Teil der Teilmengenbeziehung zu dem jeweiligen Bandalphabet darstellt. Die TM kann halt nach Definition nur Zeichen verarbeiten und nicht das Nichtvorhandensein eines Zeichens auf dem Band.
Wozu braucht man dann Zeichen, die nicht im Eingabealphabet sind, nicht das # sind, aber trotzdem auf dem Band herumlungern?
Wenn Du z.B. ein Zeichen a aus der Eingabe markieren möchtest, weil es bereits gelesen und einmal verarbeitet worden ist, es später aber nochmal verarbeiten musst, dann braucht Du im Bandalphabet ein weiteres Zeichen z.B. â. Dieses darf aber nicht im Eingabealphabet sein, sonst "weiß" die Turingmaschine ja nicht, ob es sich um ein markiertes a oder ein â aus der Eingabe handelt.
das kann man mit etwas mühe auch per '#a' rechts neben der
eingabe oder sonstwie kennzeichnen,
mit 2 zeichen, einem von der eingabe und # sollte man
eigentlich jede beliebige information speichern können,
wenn man nur ne korrekte kodierung bastelt,
mit mehr zeichen ist es natürlich 'schöner'
Die TM kann halt nach Definition nur Zeichen verarbeiten und nicht das Nichtvorhandensein eines Zeichens auf dem Band.
na klar kann die turingmaschine # lesen und darauf genauso
reagieren wie auf jedes andere symbol,
kann sicher vielfältig verwendet werden, wenn man nur will (siehe oben),
niemand sagt, dass die funktion von # nur auf die
endmarkierung beschränkt ist
aber für die ausgabe wirklich unbrauchbar ja ;)
(alles nur was ich mir so denke, genaues weiss ich nicht)
Du kannst kein # ausgeben, da dieses Symbol ja für "unbeschriftet" steht, genau so wie das lambda bei den endlichen Automaten, und jenes ist, welches den für alle Eingabealphabete entscheidenden Teil der Teilmengenbeziehung zu dem jeweiligen Bandalphabet darstellt. Die TM kann halt nach Definition nur Zeichen verarbeiten und nicht das Nichtvorhandensein eines Zeichens auf dem Band.
Würde ich nicht so sagen. Das Band wir dja mit # gefüllt, was ein ganz normales ZEichen ist. Wäre # wie Lambda, dann wäre ## = # und das ist bei einem Zustand wie q0abc##def bestimmt nicht egal. # ist auch ein Zeichen, wird hallt als Füllzeichen missbraucht [img]
http://www.fb18.de/gfx/28.gif[/img]
Du kannst kein # ausgeben, da dieses Symbol ja für "unbeschriftet" steht, genau so wie das lambda bei den endlichen Automaten, und jenes ist, welches den für alle Eingabealphabete entscheidenden Teil der Teilmengenbeziehung zu dem jeweiligen Bandalphabet darstellt. Die TM kann halt nach Definition nur Zeichen verarbeiten und nicht das Nichtvorhandensein eines Zeichens auf dem Band.
Würde ich nicht so sagen. Das Band wir dja mit # gefüllt, was ein ganz normales ZEichen ist. Wäre # wie Lambda, dann wäre ## = # und das ist bei einem Zustand wie q0abc##def bestimmt nicht egal. # ist auch ein Zeichen, wird hallt als Füllzeichen missbraucht [img]http://www.fb18.de/gfx/28.gif[/img]
Es wird dafür nicht mißbraucht, sondern gebraucht. Es ist im Bandalphabet ein ganz normales Zeichen, wenngleich es Dir schwerfallen wird z.B. Slaters Idee von "wir benutzten jetzt mal die nächsten drei # nicht, aber das vierte schon" umzusetzen. Dann muß die endliche Steuerung die notwendigen zusätzlichen Zustände liefern!
Sicher möglich, aber muß man denn alles machen, was möglich ist? Es ist halt so, daß Du, egal wie Du den Rest definierst, mindestens ein #, oder ein ' oder halt irgendetwas anderes brauchst, um die Eingabe vom Rest der Bandbeschriftung zu unterscheiden. Das # macht halt den Unterschied zwischen Eingabe- und Bandalphabet, der mindestens vorhanden sein muß, aus. Deswegen habe ich dies ja als den für
alle denkbaren Sigma und Gamma entscheidenden Punkt in der Teilmengenbeziehung von Sigma zu Gamma benannt.
das kann man mit etwas mühe auch per '#a' rechts neben der
eingabe oder sonstwie kennzeichnen,
mit 2 zeichen, einem von der eingabe und # sollte man
eigentlich jede beliebige information speichern können,
wenn man nur ne korrekte kodierung bastelt,
mit mehr zeichen ist es natürlich 'schöner'
na klar kann die turingmaschine # lesen und darauf genauso
reagieren wie auf jedes andere symbol,
kann sicher vielfältig verwendet werden, wenn man nur will (siehe oben),
niemand sagt, dass die funktion von # nur auf die
endmarkierung beschränkt ist
aber für die ausgabe wirklich unbrauchbar ja ;)
(alles nur was ich mir so denke, genaues weiss ich nicht)
Du kannst sicherlich das gelesene a löschen, an das Ende der Eingabe laufen, zwei # überspringen und dann ein a schreiben, um zu vermerken, daß Du ein a gelesen hast. Aber wo ist da der Witz, mal abgesehen davon, daß Du, um so zu verfahren, bei einer weitergehenden Verarbeitung die Anzahl der möglichen Zustände der endlichen Steuerung langsam, aber sicher, gegen unendlich steigerst?
Und dann läufst Du wieder durch die Eingabe, auf der Suche nach dem nächsten, zu verarbeitenden, a, musst leider bis zum Anfang der Eingabe, und darüber hinaus laufen,bis zum ersten von der Eingabe unterschiedlichen Bandinschrift #(welche war das noch gleich, ach ja, das sagt uns ja die endliche Steuerung, gottseidank) dann die (in der endlichen Steuerung gemerkten a's überspringen und das nächste a verarbeiten, bis ans Ende der Eingabe, die gemerkten(wieviele Zustände habe ich eigentlich in der endlichen Kontrolle??) ##a's überspringen, ….. ad infinitum
Wenn Dein Automat also die Sprache L:= {w| w enthält genausoviele a's wie b's} erkennen soll, gibt es für die Anzahl der zu merkenden a's keine obere Schranke. Ist dann die endliche Steuerung eigentlich noch endlich?
Ich gebe gern zu, daß Du für kein w aus L unendlich erreichen kannst! [img]
http://www.fb18.de/gfx/22.gif[/img]
ich dachte du wolltes das a^ auch rechts daneben schreiben,
aber dann kommt das #a gerne an die gleiche stelle wie a^
Aber wo ist da der Witz, mal abgesehen davon, daß Du, um so zu verfahren, bei einer weitergehenden Verarbeitung die Anzahl der möglichen Zustände der endlichen Steuerung langsam, aber sicher, gegen unendlich steigerst?
der witz ist (wenn die steuerung endlich bleibt),
dass ausser dem # kein weiteres zeichen ZWINGEND benötigt wird,
was die ausgangsfrage war
ich frage mich eh gerade, wie man per TM eigentlich
a^n b^n oder ähnliches bearbeitet,
hast du da mal ein praktisches beispiel?
Eine Möglichkeit ist, das erste gelesene Zeichen auf dem Eingabeband zu markieren, das entsprechende andere Zeichen auf dem Eingabeband rechts davon zu suchen. (Ich nenn die beiden jetzt mal nach der Reihenfolge a und b) Wenn unmarkiertes b gefunden, dann ebenfalls markieren, und dann zurück bis zum ersten markierten a. Dann rechts davon das nächste unmarkierte a suchen, dieses markieren und wieder zurück bis entweder # oder markiertes b, dann rechts bis entweder unmarkiertes b oder #, für # wäre dann Ende weil es mehr a's als b's gibt, etc. Wenn man auf der Suche nach einem unmarkierten a zweimal auf ein # trifft, schaut man nochmal nach, ob noch ein unmarkiertes b vorhanden ist, wenn ja akzeptiert man nicht, weil mehr b's vorhanden sind als a's, sonst ja.
Müsste so hinhauen, wenn nicht, dann Feinschliff [img]
http://www.fb18.de/gfx/15.gif[/img].
Uups, die beschriebene Sprache ist leider größer, sie enthält alle Worte, die gleich viele a's wie b's enthält, die geforderte nur die Worte, die mit n a's beginnen und genau mit n b's enden, ohne etwas dazwischen. Sorry, mit der geforderten kann man sich den Part mit dem "über die Eingabe hinaus" natürlich sparen.
ich frage mich eh gerade, wie man per TM eigentlich
a^n b^n oder ähnliches bearbeitet,
hast du da mal ein praktisches beispiel?
Genau dieses Beispiel steht im F3-Skript, Seite 26 [img]
http://www.fb18.de/gfx/23.gif[/img]
ähmm, oh, mal wieder nicht vorher nachgeschaut,
tortzdem danke
Ja, klar!
Du löscht das a ganz links, fährst dann nach rechts zur ersten Raute, einen zurück, wenn b dann löschen, wieder an den Anfang fahren und so weiter. Wenn Du grad am Anfang bist und da ebenfalls eine Raute steht (also das Band leer ist) bist Du fertig.
EDIT: Hab jetzt erst gesehen, daß dieser Thread ja ne zweite Seite hat. [img]
http://www.fb18.de/gfx/28.gif[/img] Das wäre meine Lösung gewesen…
