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 ´bar(t_M)(6)´.

Approach

Man unterscheidet folgende Fälle: Das Wort ist ein Palindrom, d.h. es gilt ´w = w^R´. Dann sind ´28´ Schritte zu absolvieren. Außerdem gibt es ´23´ Palindrome, da die ersten drei Buchstaben die letzten drei eindeutig festlegen. Das Wort hat die Form ´x_1 w x_2´ mit ´x_1 != x_2´ und ´|w| = 4´. Dann wird beim ersten Vergleich nach ´n+2 = 8´ Schritten die Arbeit beendet (und nicht akzeptiert). Es gibt zwei Möglichkeiten für ´x_1´ (´x_2´ ist dann bei binärem Alphabet festgelegt) und ´24´ Möglichkeiten für ´w´, somit ´32´ verschiedene derartige Wörter. Das Wort hat die Form ´x_1 x_2 w x_3 x_1´ mit ´x_2 != x_3´ und ´|w| = 2´. Dann erfordert der Vergleich des ersten mit dem letzten Buchstaben und der Rücklauf ´2n + 1 = 13´ Schritte und dann der Vergleich des zweiten mit dem zweitletzten Buchstaben ´(n − 2) + 2 = 6´ Schritte. Es wird also mit ´19´ Schritten abgelehnt. Es gibt jeweils zwei Möglichkeiten ´x_1´ und ´x_2´ zu wählen und vier Möglichkeiten für ´w´, insgesamt also ´16´ verschiedene Wörter. Das Wort hat die Form ´x_1 x_2 x_3 x_4 x_2 x_1´ mit ´x_3 != x_4´. Dann erfordern Vergleich des ersten und zweiten Buchstaben mit letztem und vorletztem Buchstaben und Rücklauf insgesamt ´(2n+1)+(2(n−2)+1) = 22´ Schritte. Danach wird nach ´4´ Schritten abgelehnt. Das ergibt ´26´ Schritte für ´23´ Wörter (´x_1´, ´x_2´ und ´x_3´ sind frei wählbar und bestimmen die anderen Buchstaben).


Solutions
  • ´t_M(6) = (8 * 28 + 32 * 8 + 16 * 19 + 8 * 26)/2^6 = 992/64 = 15.5´

  • Für ´xyzzyx´ (Palindrom) dauert es 28 (Häufigkeit ´0.5^3´) Für ´xyz_1z_2yx´ dauert es 26 (Häufigkeit ´0.5^3´) Für ´xy_1##y_2x´ dauert es 19 (Häufigkeit ´0.5^2´) Für ´x_1####x_2´ dauert es 8 (Häufigkeit ´0.5^1´)

    ´bar(t_M)(6) = 0.125 * 28 + 0.125 * 26 + 0.25 * 19 + 0.5 * 8 = 3.5 + 3.25 + 4.75 + 4 = 15.5´

    oder ´(8 * 28 + 2^5(7+1) + 2^4(18+1) + 2^3(25+1))/2^6´

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Calculate
  • Duration: 35min
  • Credits: 3
  • Difficulty: 0.6
  • Tags: hpi deterministic turing machine turing machine
  • Note:
    HPI, 2014-06-12, Theoretische Informatik 2, Blatt 9, Aufgabe 2
  • Created By: adius
  • Created At:
    2014-07-23 08:26:10 UTC
  • Last Modified:
    2014-07-23 08:26:10 UTC