---
title: "TM for aⁿcbⁿ (single tape, deterministic)"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-an-c-bn"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-an-c-bn
site: BCT Engineering
---

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

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2074 Asoj
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-an-c-bn
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

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}.

## 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.

## Answer

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.

| State | Read | Write | Move | Next |
|---|---|---|---|---|
| q0 | a | X | R | q1 |
| q0 | c | same | R | q4 |
| q1 | a / Y | same | R | q1 |
| q1 | c | same | R | q2 |
| q2 | Y | same | R | q2 |
| q2 | b | Y | L | q3 |
| q3 | Y / c / a | same | L | q3 |
| q3 | X | same | R | q0 |
| q4 | Y | same | R | q4 |
| q4 | ⊔ | same | S | qa |

- 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.

```text
 ┌──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
```text
[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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the TM do to the leftmost unmarked a?
   A. Replaces it with X and moves right to c
   B. Deletes it
   C. Replaces it with c
   D. Leaves it
   Answer: A. q0 marks a with X, then travels right past c to mark a matching b. (Key point: Marking)

2. After passing c, what does q2 do?
   A. Marks the first unmarked b as Y and returns left
   B. Accepts
   C. Marks c
   D. Marks the last b
   Answer: A. Each a is paired with one b by marking it Y. (Key point: Matching b)

3. When no a remains, what must the tape look like?
   A. c followed only by Y's
   B. c followed by b's
   C. only X's
   D. c followed by a's
   Answer: A. q0 sees c, moves to q4, which accepts only if the rest are Y's, i.e. all b's matched. (Key point: Final check)

4. Why is acbb rejected?
   A. Too few b's
   B. Extra b: q4 meets b with no move
   C. No c
   D. It has no a
   Answer: B. After matching one b, q4 meets an unmarked b and has no move. (Key point: Rejection)

## Related in Theory of Computation

- [Multitape TM as copying machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-copy) — Theory of Computation, chapter 4
- [Two-tape TM as binary adder](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-two-tape-binary-adder) — Theory of Computation, chapter 4
- [TM configuration; TM for palindromes](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-config-palindrome) — Theory of Computation, chapter 4
- [Define multitape Turing machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-define) — Theory of Computation, chapter 4
- [What is a Turing machine; its operation](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-define-operation) — Theory of Computation, chapter 4
- [How a universal Turing machine works](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Auniversal-tm-example) — Theory of Computation, chapter 5

## Related in other subjects

- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2
- [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2
- [Check string consists of alphabet only](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Astring-alphabet-check) — Computer Programming, chapter 7