Lösungsvorschlag
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.
ThI 1 Klausur 09/2003 Aufgabe I-5
Ich weiß, dass das hier etwas off-topic ist, aber es wird am besten sein, wenn sich die anstehenden Klausuraufgaben hier im ThI 3 Forum stehen…
Jedenfalls würde ich euch gerne meine Turing-Maschine vorstellen, die dafür konzipiert ist, die Kleiner-Relation zu berechnen. Viel Spaß damit. 
Auf dem Band steht: _ 1 1 1 1 < 1 1 1 1 1 _
Start ist beim linken Blank-Symbol.
M = (Z, {1, <}, {_, 1, <}, δ, _, {FALSE, TRUE})
δ:
S, _ → gR, _, R
gR, 1 → gR, 1, R
gR, < → gR2, <, R
gR2, 1 → gR2, 1, R
gR2, _ → dR, _, L
dR, 1 → gL, _, L
gL, 1 → gL, 1, L
gL, < → gL2, <, L
gL2, 1 → gL2, 1, L
gL2, _ → dL, _, R
dL, 1 → gR, _, R
dR, < → FALSE, <, N
dL, < → dL2, <, R
dL2, 1 → FALSE, 1, N
dL2, _ → TRUE, _, N
Anm.: gL = go left; gR = go right; dL = delete left…
Die Menge der Zustände ergibt sich aus allen hier erwähnten Zuständen…
Ich würde mich freuen, wenn jemand dazu sagen könnte, ob das Ding funktioniert oder nicht. :anx:
soweit ich das sehe müssten true und false vertauscht sein:
wenn links leer ist springt dL in dL2 und auf die rechte seite und schaut ob noch 1en da sind, wenn er noch eine findet lieferst du false => fehler( oder zu hoch für mich;-)
ausserdem sollen doch true und false teile des bandalphabets sein. also entweder da mit reinschreiben, oder du setzt 1=true und _=flase und schiebst am schluss einfach den lesekopf nach rechts vom <.
bitte auch um feedback… :ohr:
den generellen aufbau hab ich genauso gemacht. zuerst die schleife, und dann die abbruchbedingungen.
ich bin zuerst vom gutfall ausgegangen, also a,b>=1. daher kann ich im zyklus einfach an die beiden end-einser das blank schreiben; du lässt es erstmal stehen, und gehst dann rückwärts durch. ist aber im endeffekt das gleiche. dann noch die richtigen zustände rausfisseln, die eine entscheidung der relation erlauben, und gut ist…
eine zweite idee: in der mitte sukzessive die an das < symbol grenzenden 1er durch < ersetzen. also
□111<11□ ├ □11<<<1□ ├ □ 1<<<<<□
□11<1111□ ├ □ 1<<<111□ ├ □ <<<<<11□
□11<11□ ├ □1<<<1□ ├ □ <<<<<□
die hat bei mir weniger zustände (ist allerdings nicht ganz korrekt, da die maschinen einfach anhalten, wenn die entscheidung fest steht).
Generell zu LBA,PDA,TM
Prof. Strehl hat mal gemeint, dass es den Prüfer sehr sehr
mismutig stimmt, wenn man die Idee nicht dazuschreibt.
Man kann das ja in Form von Kommentaren bei den Produktionen
machen - ist sogar sehr hilfreich, wenn man noch selbst was
nachträglich hinzubauen will. Soll ja Leute geben, die bei solchen
Teilen den Überblick verlieren… so während ner Klausur … oder so.
Ja, müsste ich dann dazuschreiben. Zeit sollte ja langen für sowas.
Wie terminiert eine TM eigentlich? Kann ich einfach ein Ergebnis aus Band knallen, wo ich grad bin, und dann keine weitere Produktion vorsehen? Oder gibt’s nen speziellen ‘Rückkanal’ für sowas?
Man hat eine Menge von Endzuständen, ist die auf dem Band
stehende Eingabe abgearbeitet und die TM in einem Endzustand
dann hält sie.
Man kann sich übrigens Endzustände für “akzeptiert” “abgelehnt”
definieren, das ist manchmal nützlich.
Achso, ja, dann brauch ich gar kein True oder False aufs Band zu schreiben, sondern muss bloß in den Zustand True oder False gehen und damit ist die Maschine erlöst und der Operator hat sein Ergebnis. Korrekt so?
Genau das hab ich ja schon gemacht. Dumme Frage war das…