Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 59 ยท Turing Machines

Turing Machines for a^n b^m a^(n+m) and a^i b^j c^(i*j)

Design Turing machines for languages built from sums and products of block lengths: a^n b^m a^(n+m) and a^i b^j c^k with i*j=k. Includes state design and Python tests.

A pushdown automaton can handle sums of counts, as in PDAs for sums, but only when the blocks nest properly. Languages such as a^n b^m a^(n+m) or a^i b^j c^k with i ยท j = k are beyond a PDA: the second needs multiplication, which no stack can do. A Turing machine solves both with the technique from the arithmetic lesson: mark and restore.

Sums and products on a tape

Sum Cross off one symbol of the last block per symbol of the first two.
Product For each a, cross off one c per b, then restore the b's.

Marks X, Y, Z remember progress. Restoring marks makes a block reusable.

1 / 2

The language a^n b^m a^(n+m) (n, m โ‰ฅ 1)

Example members: abaa (n = 1, m = 1: a, b, aa) and aabaaa (n = 2, m = 1: aa, b, aaa).

The final block must be as long as the first two blocks together. The strategy is to pay off the last block, one a at a time:

  1. First block. For each a of the first block: mark it X, run right over everything until we are inside the last block, and mark its leftmost unmarked a as Z. Return to the X.
  2. Middle block. When no a of the first block is left, do the same for each b: mark it Y, mark an a of the last block as Z, return.
  3. Check. When no unmarked b is left, the last block must be completely marked: only Zs may remain until the blank.

The machine needs to know whether it is still in the first block while running right. A scanned a could belong to the first block or to the last one! The trick: the first time the head sees a b it switches to a different state (q1b), after which any a it finds belongs to the last block.

flowchart LR
    s(["s: first a"]) -->|"a โ†’ X, R"| q1(("q1: toward the b's"))
    q1 -->|"b โ†’ b, R"| q1b(("q1b: in the last block"))
    q1b -->|"a โ†’ Z, L"| q2(("q2: return"))
    q2 -->|"X โ†’ X, R"| q0(("q0: next symbol"))
    q0 -->|"a โ†’ X, R"| q1
    q0 -->|"b โ†’ Y, R"| q4(("q4: pay with b"))
    q4 -->|"a โ†’ Z, L"| q5(("q5: return"))
    q5 -->|"X,Y โ†’ same, R"| q6(("q6: next b or finish"))
    q6 -->|"b โ†’ Y, R"| q4
    q6 -->|"Z โ†’ Z, R"| q7(("q7: check Zs"))
    q7 -->|"_ โ†’ _, S"| qa((("qa")))

Only the main transitions are drawn. Runs over symbols without change (scanning right or left) are omitted.

Python Turing machine for a^n b^m a^(n+m)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The start state s exists only to insist on at least one a (n โ‰ฅ 1). After that, state q0 is the "pick the next symbol" state, which allows either another a or the first b. Without the extra start state, the string baa would wrongly slip into the b branch.

The language a^i b^j c^k with i ยท j = k (i, j, k โ‰ฅ 1)

The number of cs must equal the product of the number of as and bs. Think of two nested loops:

TEXT
for each a in the first block:        # outer loop
    for each b in the second block:   # inner loop
        cross off one c               # one unit of the product

The machine implements exactly this with marks:

  • Outer loop: mark one a as X.
  • Inner loop: mark one unmarked b as Y and cross off one unmarked c as Z, then return to the Y and continue with the next unmarked b.
  • End of the inner loop: when all bs are Y, restore them to bs so that the next a can use them again. This restoring step is the key difference from the sum machine.
  • End of the outer loop: when no a remains, the rest of the tape must be bs and Zs in order, with no unmarked c left.

If the cs run out in the middle of a round, the machine finds no unmarked c and rejects; if there are cs left at the end, the final check rejects.

Python Turing machine for a^i b^j c^(i*j)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The machine passes all 88,573 strings up to length 10 (every string over {a, b, c}). The step counts grow quickly (roughly cubic) because each of the i rounds walks over the bs and cs many times.

Why a PDA cannot do the product

A stack can count one quantity, and can compare it with another one once, because popping destroys it. For i ยท j = k we must use the count j i times, once per a. A PDA would have to remember j while also consuming it, which is impossible. The Turing machine's tape is rewritable and re-readable: marking b as Y and restoring it as b lets the same block serve every round.

This language is not even in the PDA class, but it is easily context-sensitive, as an LBA can do exactly this marking in the input's own cells.

A checklist for matching machines

  1. Choose the marks. One mark symbol per block (X, Y, Z).
  2. Define one round: which symbols are marked and where the head must return.
  3. Handle the first symbol separately when a block must not be empty (an extra start state).
  4. Use a state to remember which region the head is in when the same letter appears in two blocks.
  5. Restore marks that must be reused (products); keep them when they are consumed (sums).
  6. Check the tail: what may remain after the last round?
  7. Test exhaustively on short strings.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the machine for a^n b^m a^(n+m), why does the head switch to a new state (q1b) after seeing the first b?

    The same letter a appears in two blocks; the state records which region the head is in.
  2. 2. In the product machine for i * j = k, what is the purpose of restoring the Y marks to b?

    The inner loop must run over all j b's for each of the i a's, so the b marks must be undone after every round.
  3. 3. Why can't a PDA recognize a^i b^j c^(i*j)?

    A stack count is consumed when compared; a product needs the same count again and again.
  4. 4. What does the final check in the product machine ensure?

    If the tail contains anything except b's and Z marks (such as an unmarked c), the machine has no rule and rejects.

Summary

  • Sums such as a^n b^m a^(n+m) are decided by crossing off one symbol of the last block per symbol of the earlier blocks.
  • Products such as a^i b^j c^(iยทj) use two nested loops: the b-marks are restored after each outer round.
  • An extra start state enforces non-empty blocks; a region-tracking state tells apart a letter that occurs in two blocks.
  • Exhaustive testing against a Python predicate validates every design.
  • These languages show that Turing machines compute with the same data again and again, which stacks cannot.

Next: Recursive and recursively enumerable languages