turingmaschine Palindrom

Hoi Leute!

Brauche eure Hilfe! muss bis morgen 8:00 folgendes beispiel lösen:

Gegeben ist eine Turingmaschine mit einem Band, deren Schreib- / Lesekopf sich am linken Ende einer zusammenhängende Abfolge von 'a' und 'b' befindet (siehe Beispielsgraphik weiter unten). Gesucht ist nun ein Programm, das feststellt ob es sich bei besagter 'a'/'b' Folge um ein Palindrom handelt. Palindrome sind Wörter, die von links gelesen dasselbe ergeben wie von rechts gelesen: "abba", "babbab", "aba", etc.

Als Beispiel ist das Eingabeband mit dem Palindrom 'abbbaabbba' dargestellt:

Eingabeband.jpg schaut ca. so aus

"_ _ _ a b b b a a b b b a _ _ _ "
      Start (=linkes a)



Dein Programm ist in der Form von Tripeln anzugeben: (x steht für ein leeres Feld.)

     a    b    x (leer)
Start    x - R - Z1    x - R - Z2    x - S - Pal
Z1    ...    ...    ...
Z2    ...    ...    ...
...    ...    ...    ...
Pal    a - S - Pal    b - S - Pal    x - S - Pal
noP    a - S - noP    b - S - noP    x - S - noP

Befindet sich die Turingmaschine im links angegebenen Zustand und steht am Band das oben angeführte Symbol, so bedeutet das Tripel "Symbol - Bewegung - Zustand"...

    * Schreibe 'Symbol' auf das Band. (a / b / x)
    * Gehe einen Schritt in Richtung 'Bewegung'. (L / R / S = Links / Rechts / Stehenbleiben)
    * Wechsle in den Zustand 'Zustand'. (Start, Pal, noP, und alle Zustände, die Du sonst noch definiert hast.)

Handelt es sich bei dem gegeben Wort um ein Palindrom, dann soll Deine Turingmaschine in einem Zustand namens Pal (wie oben beschrieben) stehen bleiben. Ist das Wort kein Palindrom, soll der Endzustand noP lauten. Es ist egal, was nach Ablauf Deines Programms auf dem Band steht und wo der Schreibe-Lese Kopf sich befindet!

Beachte folgende Punkte:

    * Kann eine Kombination aus Symbol und Zustand bei Deiner Maschine nicht vorkommen, so darfst Du das entsprechende Feld freilassen (es kann hier aber auch ein beliebiger Eintrag stehen: Er wird ja sowieso nie ausgeführt).
    * Ist ein Feld freigelassen und die entsprechende Kombination tritt auf, so hält die Turing Maschine automatisch an. Falls dabei weder der Zustand Pal noch NoP erreicht wurde, dann ist die Antwort auf die Frage, ob es sich (bei korrektem Input) um ein Palindrom handelt, auf jeden Fall falsch.
    * Du darfst beliebig viele Zustände verwenden. Die Zahl Acht könnte ein guter Richtwert sein.
    * Du darfst auch beliebig viele Hilfssymbole verwenden. Vergiss aber nicht, dass es für alle Kombinationen von Zuständen und Symbolen entsprechende Felder geben muss, die aber wie gesagt auch leer sein können, falls die Turing Maschine nie in eine Situation mit dieser Kombination von Zustand und Symbol kommen kann. Du musst also - auch für Start & Co. - entsprechend viele zusätzliche Spalten anlegen.


vielleicht kann mir jem helfen!

cya Aik!