Es sei die deterministische akzeptierende 1-Band-Turing-Maschine M gegeben, die wie folgt arbeitet:
- ´M´ läuft über das Eingabewort und kopiert es auf das Arbeitsband. Dabei testet ´M´ durch einen Wechsel zwischen zwei Zuständen noch, ob das Eingabewort gerade Länge ´> 1´ hat. Ist die Eingabe leer oder ist ihre Länge ungerade, so geht ´M´ in den ablehnenden Stoppzustand.
- Hat das Wort gerade Länge bewegt sich der Kopf des Eingabebandes zurück an den Anfang der Eingabe und geht in den Zustand ´v´, wobei der Kopf des Arbeitsbandes über dem letzten Buchstaben verharrt.
- Wird nun auf dem Eingabeband und dem Arbeitsband der gleiche Buchstabe ´x != **´ gelesen, verbleibt ´M´ in ´v´, bewegt den Kopf über der Eingabe eine Position nach rechts und den des Arbeitsbandes um eine Position nach links. Wird auf Eingabe- und Arbeitsband ein verschiedener Buchstabe gelesen, geht ´M´ in den ablehnenden Stoppzustand. Wird auf Eingabe- und Arbeitsband ´**´ gelesen, so geht ´M´ in den akzeptierenden Stoppzustand.
Bestimme für diese Turing-Maschine die Durchschnittskomplexitäten ´bar(t_M)(n)´ und ´bar(s_M)(n)´ für ´n >= 0´ und ein binäres Alphabet.
Für ungerade n erhält man:
´bar(t_M)(n) = (sum_(|w|=n) n+1)/(2^n) = (2^n(n+1))/(2^n) = n + 1´
und
´bar(s_M)(n) = n + 1´
Für gerade n ergibt sich:
´bar(t_M)(n) = (2^(n/2)(3n+3) + sum_(k=1)^(n/2) 2^(n-k) (2n+2+k))/(2^n)´ ´= (2^(n/2)(3n+3) + (2n+2)sum_(k=1)^(n/2) 2^(n-k) + sum_(k=1)^(n/2) 2^(n-k)k)/(2^n)´ ´= (2^(n/2)(3n+3) + (2n+2) 2^(n/2) sum_(k=1)^(n/2) 2^(n/2-k) + sum_(k=1)^(n/2) 2^(n-k)k)/(2^n)´ ´= (2^(n/2)(3n+3) + (2n+2) 2^(n/2) sum_(k=0)^(n/2-1) 2^k + sum_(k=1)^(n/2) 2^(n-k)k)/(2^n)´ ´= (2^(n/2)(3n+3) + (2n+2) 2^(n/2) (2^(n/2)-1) + 2 * 2^n - 2^(n/2) (n/2+2))/(2^n)´ ´= (2^n(2n+4) + 2^(n/2)(n/2-1))/(2^n)´ ´= 2n + 4 + (n/2-1)/(2^(n/2))´
´bar(s_M)(n) = (2^(n/2)(n+2)+(2^n - 2^(n/2))(n+1))/(2^n) = n + 1 + 1/2^(n/2)´
(da bei ´w = w^R´ die ersten ´n/2´ Buchstaben, die letzten ´n/2´ Buchstaben eindeutig bestimmen, gibt es ´2^(n/2)´ Wörter mit ´w = w^R´. Bei Unterschied im ´k´. Buchstaben bestimmen die ersten ´k´ Buchstaben eindeutig die letzten ´k´ Buchstaben, die verbleibenden ´n − 2k´ Buchstaben sind frei wählbar, woraus ´2^k * 2^(n−2k) = 2^(n−k)´ mögliche Wörter resultieren. Mit diesem Hinweis:
Für ´n >= 2´ gilt ´sum_(r = 1)^(n - 1) r2^(n − r − 1) = 2^n - n - 1´
ergibt sich letztendlich:
´sum_(k=1)^(n/2) 2^(n-k)k = 2^(n/2+1) sum_(k=1)^(n/2) 2^(n/2-k-1)k = ´´2^(n/2+1) (2^(n/2-n/2-1) n/2 + sum_(k=1)^(n/2-1) 2^(n/2-k-1) k) = ´´2^(n/2+1) (n/(2*2) + 2^(n/2) - n/2 - 1) = ´´2 * 2^n - 2^(n/2)(n/2+2)´
´n = 0´ ´s(M) = 0´ ´t(M) = 1´
´n´ ist ungerade ´s(M) = n + 1´ ´t(M) = n + 1´
´n´ ist gerade Bei ´s(M)´ ist es entweder ´n+2´ bei Palindrom oder ´n+1´ bei nicht Palindrom. Ist das Wort ´n´ lang dann gibt es ´2^n´ Wörter und ´2^(n/2)´ Möglichkeiten eines Palindromes und daher auch ´(2^n - 2^(n/2))´ nicht-Palindrome.
´s(M) = (2^(n/2) * (n+2) + (2^n - 2^(n/2)) * (n+1)) / 2^n´ ´= …´ ´= n + 1 + 1/(2^(n/2))´
HPI, 2014-06-12, Theoretische Informatik 2, Blatt 9, Aufgabe 1
2014-07-23 08:20:57 UTC
2014-07-23 08:20:57 UTC