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
12.2
-
- Beiträge: 34
- Registriert: Do 13. Nov 2008, 16:30
Re: 12.2
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?
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?
Folge dem und du wirst den Weg der Permutation finden
Re: 12.2
"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
mfG
Markus
-
- Beiträge: 34
- Registriert: Do 13. Nov 2008, 16:30
Re: 12.2
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...
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...
Folge dem und du wirst den Weg der Permutation finden
Re: 12.2
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,>
Überzeug dich selbst ...
mfG
Markus