Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum: a)

Question

Hier finden Sie eine Auflistung von alternativen Lösungsvorschlägen inkl. Beurteilung aus dem alten ILIAS-Forum (vor WS1516).

Dieser Post wurde der Übersichtlichkeit halber erstellt, um die alternativen Lösungsvorschläge aus dem alten ILIAS-Forum nicht überzubetonen. Wenn Sie neue alternative Lösungsvorschläge diskutieren wollen, sollten Sie eine neue Frage erstellen - und NICHT hier posten!

 

Answer 1

Ich habe versucht die Aufgabe ohne # zulösen. Meine Idee ist ganz ähnlich nur, dass ich zuerst das Zeichen nach dem \$ einlese, dieses lösche und dann schaue ob dasselbe Zeichen am Anfang des Wortes steht. Wenn ja wird gelöscht und es wird von vorne begonnen (Einlesen des 1. Zeichens nach \$), wenn nein bricht der Automat ab. Bei einem korrekten Wort bleibt somit nur \$ übrig. Bzw. \( \lambda \$ \lambda \)

Ich habe dazu folgende Zustandsübergänge:

Mit T = ({0,1,\$},{0,1,\$},{s0,s1,...,s5,sE},siehe oben,s0,sE)

Ist die Lösung auch korrekt? Vielen Dank.

Hier sind die Zustandsübergänge:

Comments

Zunächst: Bei einer TM wird * für leere Stellen auf Band verwendet. (s1, 0) \( \rightarrow \) (s2, \( \lambda \) , L) würde heißen, du schreibst den Buchstaben \( \lambda \) auf das Band, nicht das leere Wort (ist erlaubt, muss dann aber in B enthalten sein)!

Selbst wenn man alle \( \lambda \) durch * ersetzt, hält die TM im Endzustand an, wenn direkt hinter dem \$ * steht. Wenn ein Eintrag mit * überschrieben wird, wird die Bandinschrift rechts davon NICHT um eins nach links verschoben, d.h. wenn du in 101\$101 die 1 nach dem \$ mit * überschreibst, steht danach 101\$*01 (und nicht 101\$01) auf dem Band! Du müsstest also diesen Fall behandeln (Schwierigkeit: herausfinden, ob rechts von dem *  noch etwas steht oder ob man die Eingabe komplett abgearbeitet hat) oder die restlichen Zeichen explizit verschieben (was vermtl. auch recht aufwendig wird).

Gruß,

Tobias (Tutor)

Answer 2

Hallo,

ich habe die Aufgabe auch ohne das # gelöst. Bei einem richtigen Wort geht die Turingmaschine in den Endzustand, bei einem falschen ist sie nicht definiert. Nur bei einem Wort = x \$ * läuft die Turingmaschine unendlich weiter nach rechts, hält also nicht. Ist das auch erlaubt bzw. richtig?
Kleine Korrektur: (s1, *) -> (s1, *, R) ist Quatsch und muss weg.
Danke, Gruß!

 

Comments

Vorweg: ich kann keine verbindlichen Aussagen zur Klausurbewertung machen.

Deine TM läuft nicht nur bei x \$ * endlos sondern auch bei leeerer Eingabe und bei allen Eingaben, wo hinter dem \$ weniger Zeichen stehen als davor (TM läuft in s2 bzw. s6 endlos nach rechts, um ein nicht existierendes Zeichen zu suchen...).

Wenn eine Akzeptor-TM nicht halten muss, falls das Wort nicht in der Sprache liegt, ist das äußerst unpraktisch, da man ja -solange die TM läuft- nicht weiß, ob das Wort akzeptiert wird oder nicht. Selbst wenn die TM nach 10 Jahren noch läuft, kann ich mir nicht sicher sein, ob sie nicht in der nächsten Sekunde im Endzustand anhält... Daher würde ich lieber nicht davon ausgehen, dass deine (verbesserte) TM in der Klausur die volle Punktzahl erhält.

Mir ist gerade noch was an deiner TM aufgefallen: sie akzeptiert Wörter, bei denenn nach x \$ x noch irgendwelche Zeichen folgen (Beispiel: 0\$01 ). Solche Wörter sind aber nicht in der Sprache!

Gruß,

Tobias (Tutor)

Answer 3

Hallo,

könnte man die abgearbeiteten Zeichen vor dem \$ nicht direkt löschen und nur die danach mit # markieren? Dann bräuchte man auch nur sZ anstelle von sZ und sZZ. Auch verstehe ich nicht ganz, wieso man die Zustände sL UND sR benötigt. Ich habe in meiner Turingmaschine einen Zustand sÜ definiert, der überprüft, ob nachdem sich rechts von dem \$ keine Zeichen (also nur noch *) befinden (also alles abgearbeitet wurde), auch links davon schon alle Zeichen abgearbeitet wurden (also nur noch ##...#*).
Hier ein Bild meines Zustanddiagramms:
(sE entspricht sAKZ, also dem Endzustand)

Ist das so auch richtig?

Comments

Hallo,

in deine Turingmaschine haben sich ein paar kleine Fehler eingeschlichen.

1. Du löschst links vom \$ und ersetzt rechts Stück für Stück durch #. ;)

2. Von \(S_{val_{0}}\) muss man bei einer 1 auch eine 1 schreiben.

(\(S_{val_{0}}\), 1) -> (\(S_{val_{0}}\), 1, r)

3. Von \(S_{Z}\) muss man bei einer # auch eine # schreiben:

(\(S_{Z}\), #) -> (\(S_{Z}\), # l)

 4. Deine Turingmaschine geht in Zustand \(S_{Ü}\) nachmal von rechts (#) über das \$ zum *. Hier fehlt der Übergang,

(\(S_{Ü}\), \$) -> (\(S_{Ü}\), \$, l)

sonst erreicht sie nie die und wechselt auch nie in den Endzustand.

Hier zum Ausprobieren:

http://morphett.info/turing/turing.html

Meine korrigierte Version, die funktionieren sollte (* durch x ersetzt):

0 0 x r 1
0 1 x r 2
0 \$ \$ r 6
1 0 0 r 1
1 1 1 r 1
1 \$ \$ r 3
2 0 0 r 2
2 1 1 r 2
2 \$ \$ r 4
3 0 # l 5
3 # # r 3
4 1 # l 5
4 # # r 4
5 0 0 l 5
5 1 1 l 5
5 \$ \$ l 5
5 # # l 5
5 x x r 0
6 \$ \$ l 6
6 # # l 6
6 x x n halt

Drüber hinaus muss noch ein weiterer Zustand definiert werden, der überprüft, ob der rechte Teil nicht länger ist, als der linke. Die obige Touringmaschine akzeptiert nämlich auch 101\$1011:

Daher hier nochmals eine angepasste Version (du musst Wörter der Form 101\$101x verwenden, da ja x für das * steht:

0 0 x r 1
0 1 x r 2
0 \$ \$ r 7
1 0 0 r 1
1 1 1 r 1
1 \$ \$ r 3
2 0 0 r 2
2 1 1 r 2
2 \$ \$ r 4
3 0 # l 5
3 # # r 3
4 1 # l 5
4 # # r 4
5 0 0 l 5
5 1 1 l 5
5 \$ \$ l 5
5 # # l 5
5 x x r 0
6 \$ \$ l 6
6 # # l 6
6 x x n 7
7 \$ \$ r 7
7 # # r 7
7 x x n halt

Ich hoffe diese ist jetzt korrekt (in Anbetracht der "späten" Stunde)

Viele Grüße

Christoph (Tutor)

---

Danke für die Verbesserung meiner dummen Fehler und den Link zum Simulator!

Ich glaube, es funktioniert auch so:

0 0 x r 1
0 1 x r 2
0 \$ \$ r 6
1 0 0 r 1
1 1 1 r 1
1 \$ \$ r 3
2 0 0 r 2
2 1 1 r 2
2 \$ \$ r 4
3 0 # l 5
3 # # r 3
4 1 # l 5
4 # # r 4
5 0 0 l 5
5 1 1 l 5
5 \$ \$ l 5
5 # # l 5
5 x x r 0
6 # # r 6
6 _ _ n halt

also doch nur 6 Zustände, aber (vorletzte Zeile): \(S_{Ü}\), #) \(\rightarrow\) (\(S_{Ü}\), #, R). (statt wieder nach links, das war auch ein Fehler von mir). Nach dem Erreichen von \(S_{Ü}\) befindet sich der Schreibkopf auf dem Zeichen rechts neben \$ und sie erreicht den Endzustand nur, wenn auf die #s direkt ein * folgt.
Viele Grüße!