Es sei folgende deterministische akzeptierende Turing-Maschine gegeben:

´M = ({a, b}, {z_0 , z_1 , z_a , z_b , z_a^' , z_b^' , q, q'}, z_0 , {q, q'}, {q}, delta)´

mit

´delta´ ´z_0´ ´z_1´ ´z_a´ ´z_b´ ´z_a^'´ ´z_b^'´
´**´ ´(q, **, N )´ ´(z_0, **, R)´ ´(z_a^', **, L)´ ´(z_b^', **, L)´ ´(q, **, N )´ ´(q, **, N )´
´a´ ´(z_a, **, R)´ ´(z_1, a, L)´ ´(z_a, a, R)´ ´(z_b, a, R)´ ´(z_1, **, L)´ ´(q', a, N )´
´b´ ´(z_b, **, R)´ ´(z_1, b, L)´ ´(z_a, b, R)´ ´(z_b, b, R)´ ´(q', b, N )´ ´(z_1, **, L)´

Bestimme:

  1. ´T(M)´.
  2. ´t_M(w)´ und ´s_M(w)´ für ´w = "aabbba"´ und ´w = "abaaba"´
  3. ´s_M(n)´ für ´n >= 0´
  4. ´t_M(6)´
Approach

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

<s>Missing</s>


Solutions
    1. ´T(M) = {w | w = wR }´
    2. ´t_M(w)´:
      • ´t_M("aabbba") = 19´
      • ´t_M("abaaba") = 28´
    3. ´t_M(n) = n^2/2 + 3/2 n + 1´
  • Teil 1

    Die Turingmaschine akzeptiert Palindrome.

    ´T(M) = {w | w in Sigma^(**) ^ w = w^R}´

    Teil 2

    ´z_0´: Erste Buchstaben durch Zustand z_a bzw. z_b merken und dann löschen ´z_a´ bzw. ´z_b´: Durchlaufen bis ´**´, dann nach ´z_a^'´ bzw. ´z_b^'´ ´z_a^'´ bzw. ´z_b^'´: Lesekopf steht über letztem Buchstaben, bei jeweils anderem Buchstaben Abbruch, sonst ´z_1´ ´z_1´: Zurück zum Anfang ´z_0´

    ´w = "aabbba"´

    • 7x nach rechts gehen
    • 6x nach links gehen
    • 5x rechts gehen
    • 1x Abbruch

    => ´t_M(w) = 19´ => ´s_M(w) = 7´

    ´w = "abaaba"´

    • 7x nach rechts gehen
    • 6x nach links gehen
    • 5x rechts gehen
    • 4x nach links gehen
    • 3x rechts gehen
    • 2x nach links gehen
    • 1x rechts gehen

    => ´t_M(w) = 28´ => ´s_M(w) = 7´

    ´O(n^2)´ Schleife Platzkomplexität nicht definiert!

    Teil 3

    ´t_M(w) = sum_(n=1)^(n+1) k = ((n+1)(n+2))/2´ ´s_M(w) = n+1´

    Teil 4

    ´t_M(6) = 28´

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Calculate
  • Duration: 45min
  • Credits: 8
  • Difficulty: 0.7
  • Tags: hpi turing machine deterministic turing machine time complexity space complexity
  • Note:
    HPI, 2014-05-26, Theoretische Informatik 2, Blatt 8, Aufgabe 2
  • Created By: adius
  • Created At:
    2014-07-22 19:53:14 UTC
  • Last Modified:
    2014-07-22 19:53:14 UTC