12.2

[Nanatsusaia]

Auch wenns nicht so schwer ist, hier ein kleiner Tipp zur a) und b).

Die Idee bei der a) ist, zuerst ein "bc" zu suchen. Falls das vohanden ist, makiert man sich das c (z.B: als X), loopt man ans Ende des Wortes und verschiebt jedes Wort um eins nach rechts. Das solange bis man ans X kommt. Das X wieder zu c umbennenn, in das entstandene leere Feld nach dem c ein a einfügen und wieder zum Anfang gehen. Das wird solange wiederholt, bis das Wort fertig ist.

Zur b): ein jedes wort wird verdoppelt. d.h. aus "a" wid "aa" oder aus "ab" wird "abab". Wie ihr das hinschreibt überlass ich euch

Schönen abend noch
Nana

[Chrisor]

bei der b muss ich dich korrigieren. aus ab wird nicht abab, sondern abba

[CansaSCity]

Wie wollt ihr denn da drauf gekommen sein?

also wenn man ein ganz normales wort w {a,b}* eingibt, dann sieht das bei abab so aus:

Z 0.............0...............0...............0................0..............1
B abab -> !abab -> !a!bab -> !a!b!ab -> !a!b!a!b_ -> !a!b!a!b


so und was ist macht die Touringmaschine dann laut Tabelle... sie Terminiert oder etwa nicht?

[markusj]

"Male" dir mal den Automaten auf und sieh dir scharf an was er macht - tatsächlich wird einfach ein Palindrom der Länge 2w erzeugt, dessen erste Hälfte w ist (und dementsprechend ist die zweite Hälfte w rückwärts gelesen).

mfG
Markus

[CansaSCity]

Was denkst du denn dass ich da gemacht habe?
Ich habe ein konkretes beispiel durchlaufen lassen und da terminiert die Maschine nach dem es alle b in !b und alle a in !a umgewandelt hat.

Dann schreib doch mal ein beispiel für dein Palindrom auf...

[markusj]

Code: Alles auswählen

1,_,2,_,<
1,a,1,c,>
1,b,1,d,>
1,c,1,c,>
1,d,1,d,>
2,_,6,_
2,a,2,a,<
2,b,2,b,<
2,c,3,a,>
2,d,4,b,>
3,_,2,a,<
3,a,3,a,>
3,b,3,b,>
3,c,3,c,>
3,d,3,d,>
4,_,2,b,<
4,a,4,a,>
4,b,4,b,>
4,c,4,c,>
4,d,4,d,>

Turing Machine Simulator

Überzeug dich selbst ...

mfG
Markus