Teil 1

Die Maschine arbeitet wie folgt: Das Leerwort wird direkt akzeptiert. Bei einem Wort der Länge ´1´ wird bei Lesen von ´x´ das ´x´ gelöscht und in den Zustand ´z_x´ gewechselt, in dem nun sofort das ´**´ hinter dem Wort gelesen wird. Dann wird nach links gegangen und in ´z_x^'´ gewechselt. Nun wird ´**´ gefunden und akzeptiert. Bei einem Wort der Länge ´n >= 2´ wird zuerst ein ´x´ gelesen, dieses gelöscht und in ´z_x´ gewechselt. Nun wird ans Wortende gelaufen und in ´z_x^'´ gewechselt. Es wird geprüft, ob ´x´ auf dem Band steht. Im positiven Fall wird ´x´ am Ende gelöscht und an den Wortanfang zurückgegangen (das Wort auf dem Band ist nun um zwei Buchstaben kürzer). Nun wird wieder bei ´z_0´ gestartet. Im negativen Fall wird das Wort abgelehnt. Es erfolgt nur Akzeptanz, wenn nun das Wort ´x_2 x_3 … x_(n−1)´ akzeptiert wird.

Damit ergibt sich mittels Induktion sofort, dass ein Wort genau dann akzeptiert wird, wenn ´w = wR´ gilt. Somit gilt:

´T(M) = {w | w = wR }´

Teil 2

´w = "aabbba"´ Für das Laufen über das Wort und den Vergleich des ersten und letzten Buchstaben benötigt man ´n + 2 = 8´ Schritte. Die Rückkehr zum Anfang erfordert ´n − 1 = 5´ Schritte. Nun steht ´"abbb"´ auf dem Band. Das Laufen zum Ende erfordert ´5´ Schritte und der anschließende Vergleich (´1´ weiterer Schritt) beendet die Arbeit. Wir benötigen also ´19´ Schritte, also gilt ´t_M("aabbba") = 19´.

´w = "abaaba"´ Für das Laufen über das Wort und den Vergleich des ersten und letzten Buchstaben benötigt man ´n + 2 = 8´ Schritte. Die Rückkehr zum Anfang erfordert ´n − 1 = 5´ Schritte. Insgesamt werden ´13´ Schritte benötigt. Jetzt ist ´w = baab´ der Länge ´n' = 4´ zu untersuchen, wofür wir ´n' + 2 + n' − 1 = 9´ Schritte benötigen. Nun steht ´w = aa´ auf dem Band. Hierfür werden ´5´ Schritte abgearbeitet. Jetzt steht das Leerwort auf dem Band, dass sofort (´1´ Schritt) akzeptiert wird. Insgesamt werden ´28´ Schritte absolviert, also ´t_M(abaaba) = 28´.

Teil 3

Offenbar liegt der schlechteste Fall vor, wenn ´w = wR´ gilt. Im Fall des Leerwortes brauchen wir einen Schritt. Im Fall des Wortes der Länge ´1´ benötigen wir nach 1. ´3´ Schritte. Haben wir ein Wort der Länge ´n´, so erreichen wir nach ´2n+1´ Schritten ein um zwei Buchstaben kürzeres Wort, das zu untersuchen ist. Dies bedeutet ´t_M(n) = 2n + 1 + t_M(n − 2)´. Mittels Induktion ist nun leicht zu beweisen, dass gilt:

´t_M(n) = n^2/2 + 3/2 n + 1´ für gerades und ungerades n

(Um auf die Formel zu kommen: Es ist klar, dass ´t_M(n) = alpha n^2 + beta n + gamma´ gelten muss, und aus den Werten für kleine ´n´ bestimmt man ´alpha´, ´beta´ und ´gamma´.)

Teil 4

Missing