Gib eine akzeptierende Turing-Maschine an, die die Sprache ´{a^(2^n) | n >= 0}´ akzeptiert.

Approach

Damit eine Potenz von 2 vorliegt, muss bei fortgesetztem Halbieren stets wieder eine gerade Zahl entstehen, bis zum Schluss 1 übrig bleibt. Dies wird wie folgt umgesetzt: Wir ersetzen jedes zweite Vorkommen von ´a´ durch ´b´ und beachten, dass eine gerade Anzahl von ´a´s übrig bleibt (Zustände ´z'_1´ und ´z'_0´ ), laufen zurück (Zustand ´z_2´). Dieser Vorgang wird iteriert. Zu beachten ist der Spezialfall, dass nur noch ein ´a´ auf dem Band steht (Zustand ´z_1´).


Solutions

  • Es ergibt sich folgende Turing-Maschine:

    ´M = ({a, b}, {z_0, z'_0, z_1, z'_1, z_2, q_1, q_2}, z_0, {q_1, q_2}, delta, {q_1})´

    mit

    ´delta´ ´z_0´ ´z_1´ ´z'_0´ ´z'_1´ ´z_2´
    ´**´ ´(q_2, **, N)´ ´(q_1, **, N)´ ´(z_2, **, L)´ ´(q_2, **, N)´ ´(z0, **, R)´
    ´a´ ´(z_1, a, R)´ ´(z'_0, b, R)´ ´(z'_1, a, R)´ ´(z'_0, b, R)´ ´(z_2, a, L)´
    ´b´ ´(z_0, b, R)´ ´(z_1, b, R)´ ´(z'_0, b, R)´ ´(z'_1, b, R)´ ´(z_2, b, L)´

  • Idea: Every time we return to stage 1, the number of 0’s on the tape is halved.

    Pseudocode:

    1. Sweep from left to right, cross out every other 0
    2. If in stage 1, the tape had only one 0, accept
    3. If in stage 1, the tape had an odd number of 0’s, reject
    4. Move the head back to the first input symbol
    5. Go to stage 1

    ´M = ({a, x}, {z_0, z_1, z_2, z_3, z_4}, z_0, {q_1, q_2}, delta, {q_1})´

    ´bb delta´ | ´z_0´ | ´z_1´ | ´z_2´ | ´z_3´ | ´z_4´ ---|---|---|---|---|---|--- ∗ | ´(q_2,∗,N)´ | ´(q_1,∗,N)´ | ´(z_3,∗,L)´ | ´(z_1,∗,R)´ | ´(q_2,∗,N)´ a | ´(z_1,∗,R)´ | ´(z_2,x,R)´ | ´(z_4,a,R)´ | ´(z_3,a,L)´ | ´(z_2,x,R)´ x | ´(q_2,x,N)´ | ´(z_1,x,R)´ | ´(z_2,x,R)´ | ´(z_3,x,L)´ | ´(z_4,x,R)´

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Name
  • Duration: 35min
  • Credits: 4
  • Difficulty: 0.6
  • Tags: hpi turing machine
  • Note:
    HPI, 2014-04-01, Theoretische Informatik 2, Aufgabe 2
  • Created By: adius
  • Created At:
    2014-07-21 13:06:42 UTC
  • Last Modified:
    2014-07-21 13:10:26 UTC