Gib eine akzeptierende Turing-Maschine an, die die Sprache ´{a^n b^n c^n | n >= 1}´ akzeptiert.

Approach

Wir ersetzen beim Laufen über das Wort stets das erste ´a´, ´b´ und ´c´ durch ´d´ und testen dabei noch, ob das Eingabewort die Form ´a^r b^s c^t´ mit ´r, s, t >= 1´ hat und danach das Wort auf dem Band die Form ´d^(r') a^r d^(s') b^s d^(t') d^t´ mit ´r, s, t >= 1´ und ´r', s', t'´ hat (Zustände ´z_a´ und ´z_a^'´ zeigen an, dass ´a´ ersetzt wurde, ´z_b´ und ´z_b^'´ zeigen an, dass ein ´b´ ersetzt wurde, ´z_c´ und ´z_1´ zeigen an, dass ein ´c´ ersetzt wurde) und laufen an den Wortanfang zurück (Zustand ´z_1´) und beginnen von vorne.


Solutions

  • Es ergibt sich folgende Turing-Maschine:

    ´M = ({a, b, d}, {z_0, z_0^', z_1, z_a, z_a^', z_b, z_b^', z_c, q_1, q_2}, z_0, {q_1, q_2}, delta, {q_1})´

    mit

    ´delta´ ´z_0´ ´z_0^'´ ´z_1´ ´z_a´ ´z_a^'´ ´z_b´ ´z_b^'´ ´z_c´
    ´**´ ´(q_2, **, N)´ ´(q_1, **, N)´ ´(z_0^', **, N)´ ´(q_2, **, N)´ ´(q_2, **, N)´ ´(q_2, **, N)´ ´(q_2, **, N)´ ´(z_1, **, L)´
    ´a´ ´(z_a , d, R)´ ´(z_a^', d, R)´ ´(z_1, a, L)´ ´(z_a, a, R)´ ´(z_a^', a, R)´ ´(q_2, a, N)´ ´(q_2, a, N)´ ´(q_2, a, N)´
    ´b´ ´(q_2,b,N)´ ´(q_2,b,N)´ ´(z_1,b,L)´ ´(z_b,d,R)´ ´(z_b^',d,R)´ ´(z_b,b,R)´ ´(z_b^', b, R)´ ´(q_2,b,N)´
    ´c´ ´(q_2,c,N)´ ´(q_2,c,N)´ ´(z_1,c,L)´ ´(q_2,c,N)´ ´(q_2,c,N)´ ´(z_c,d,R)´ ´(z_1,d,L)´ ´(z_c,c,R)´
    ´d´ ´(q_2, d, N)´ ´(z_0^', d, R)´ ´(z_1, d, L)´ ´(q_2, d, N)´ ´(z_a^',d,R)´ ´(q_2, d, N)´ ´(z_b^', d, R)´ ´(q_2, d, N)´

  • Pseudocode:

    1. If first symbol == blank: REJECT
    2. If first symbol == b or c: REJECT
    3. If first symbol == a:
      1. Write x over a and move right.
      2. If current symbol is a or y, move right until you see b if other symbol: REJECT
      3. Write y over b. Skip b’s and z’s until you see c if other symbol REJECT
      4. Write z over c Rewind back to rightmost x
    4. If you see an a, go to 3.1 If you see y, rewind and check if the tape only has x's, y's, z's => If so, ACCEPT, otherwise REJECT.

    Turingmaschine:

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

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Name
  • Duration: 35min
  • Credits: 6
  • Difficulty: 0.6
  • Tags: hpi turing machine
  • Note:
    HPI, 2014-04-01, Theoretische Informatik 2, Aufgabe 3
  • Created By: adius
  • Created At:
    2014-07-21 13:31:12 UTC
  • Last Modified:
    2014-07-24 10:11:29 UTC