Skip to main content

TM for aⁿcbⁿ (single tape, deterministic)

Short answer

The TM marks the leftmost a with X, moves past c, marks the first b with Y, returns to the left, and repeats. When no a remains, it checks that c is next and all remaining are Y's, accepting; otherwise rejects.

Design a single tape deterministic Turing machine which accepts all strings defined for the language {aⁿcbⁿ, n ≥ 0} over the alphabet {a, b, c}.

L = { aⁿcbⁿ : n ≥ 0 } over {a, b, c}.

Idea. Repeatedly mark the leftmost unmarked a with X, move right past c, mark the first unmarked b with Y, and return to the left. When no a remains, the next symbol must be c and everything after it must be marked b's (Y).

M = (Q, {a,b,c}, {a,b,c,X,Y,⊔}, δ, q0, ⊔, {qa}), Q = {q0, q1, q2, q3, q4, qa}, deterministic, single tape.

StateReadWriteMoveNext
q0aXRq1
q0csameRq4
q1a / YsameRq1
q1csameRq2
q2YsameRq2
q2bYLq3
q3Y / c / asameLq3
q3XsameRq0
q4YsameRq4
q4⊔sameSqa
  • q0: look for the next a (or c if none left).
  • q1: move right to c. q2: move right to the first unmarked b.
  • q3: go back left to X. q4: final check that only Y's follow c.
 ┌──q0──a/X,R──►q1──c/c,R──►q2──b/Y,L──►q3
 │    ▲   (a,Y: R)   (Y: R)        │  (Y,c,a: L)
 │    └────────── X/X,R ───────────┘
 └─ c/c,R ─► q4 ──(Y: R)── ⊔ ──► ((qa))

Processing aacbb

[q0]aacbb -> X[q1]acbb -> Xac[q2]bb -> Xa[q3]cYb -> [q3]XacYb
-> X[q0]acYb -> XX[q1]cYb -> XXcY[q2]b -> XXc[q3]YY -> XX[q0]cYY
-> XXc[q4]YY -> XXcYY[q4]⊔ -> qa (accept)

Strings such as aacb (too few b's: q2 meets ⊔), acbb (extra b: q4 meets b) and acbc are rejected because no move is defined. The input c alone (n = 0) goes q0 → q4 → qa and is accepted.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 4 questions →