---
title: "TM for equal numbers of x, y, z"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:tm-equal-xyz"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-equal-xyz
site: BCT Engineering
---

# TM for equal numbers of x, y, z

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2073 Shrawan
- 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-equal-xyz
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Design a TM for L = {w ∈ {x,y,z}* : w has an equal number of x's, y's and z's}. Verify for #xyxyzz#.

## Short answer

The TM makes passes, crossing out one x, one y, one z per pass by overwriting with X,Y,Z. After all passes, if no unmarked x,y,z remain, it accepts. For #xyxyzz#, two passes produce #XYXYZZ#; no unmarked symbols, so accepted.

## Answer

L = { w ∈ {x,y,z}* : #x = #y = #z }. The delimiter # marks both ends of the input.

**Idea.** Make passes over the tape. In each pass, cross out one x (to X), then one y (to Y), then one z (to Z), returning to the left # after each. When no x remains, check that no y or z is left either; if the tape contains only X, Y, Z, accept.

| State | Read | Write | Move | Next |
|---|---|---|---|---|
| q0 | # | same | R | q1 |
| q1 | y / z / X / Y / Z | same | R | q1 |
| q1 | x | X | L | r1 |
| q1 | # | same | L | rC |
| r1 | x / y / z / X / Y / Z | same | L | r1 |
| r1 | # | same | R | q2 |
| q2 | x / z / X / Y / Z | same | R | q2 |
| q2 | y | Y | L | r2 |
| r2 | x / y / z / X / Y / Z | same | L | r2 |
| r2 | # | same | R | q3 |
| q3 | x / y / X / Y / Z | same | R | q3 |
| q3 | z | Z | L | r3 |
| r3 | x / y / z / X / Y / Z | same | L | r3 |
| r3 | # | same | R | q1 |
| rC | x / y / z / X / Y / Z | same | L | rC |
| rC | # | same | R | qD |
| qD | X / Y / Z | same | R | qD |
| qD | # | same | S | qa |

- q1: find an unmarked x. q2: find an unmarked y. q3: find an unmarked z. (r1, r2, r3 return to the left # after each.)
- rC / qD: when no x is left, rewind and check that the whole tape holds only X, Y, Z.

If q2 or q3 cannot find a y or z (reaches #), there is no move, so the machine rejects.

#### Verification for #xyxyzz# (2 x's, 2 y's, 2 z's)
```text
Pass 1:  mark x, y, z   -> #XYxyZz#
Pass 2:  mark x, y, z   -> #XYXYZZ#
q1 sweeps right and finds no x (reaches #): rewind with rC,
qD scans X Y X Y Z Z and meets # : accept
```
Selected configurations (⊢* means several moves): #[q1]xyxyzz# ⊢* #[q2]Xyxyzz# ⊢* #[q3]XYxyzz# ⊢* #[q1]XYxyZz# ⊢* #[q2]XYXyZz# ⊢* #[q3]XYXYZz# ⊢* #[q1]XYXYZZ# ⊢* #XYXYZZ[q1]# ⊢* #[qD]XYXYZZ# ⊢* #XYXYZZ[qD]# ⊢ #XYXYZZ[qa]#.

**#xyxyzz# is accepted.** A string like #xxyz# fails: after pass 1 gives #XxYZ#, pass 2 crosses out the second x, but no y remains, so q2 reaches # and halts without accepting.

## Check yourself

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

1. What does each pass of the TM do?
   A. Crosses out one x, one y and one z
   B. Crosses out all x's
   C. Counts the symbols in binary
   D. Reverses the string
   Answer: A. Each pass marks one of each symbol so equal counts are checked. (Key point: Strategy)

2. When no x remains, how does the machine decide?
   A. Accepts immediately
   B. Rewinds and accepts only if the tape contains just X, Y, Z
   C. Rejects
   D. Starts over
   Answer: B. Any leftover y or z means unequal counts. (Key point: Acceptance check)

3. Why is #xxyz# rejected?
   A. It has no x
   B. After crossing both x's no y remains, so q2 hits # with no move
   C. It has a z
   D. The # is missing
   Answer: B. There are more x's than y's, so a pass cannot find a y. (Key point: Rejection)

4. What are r1, r2, r3 used for?
   A. Returning to the left # after each marking
   B. Accepting
   C. Marking z
   D. Checking the end
   Answer: A. They rewind the head so the next search begins from the left end. (Key point: Return states)

## Related in Theory of Computation

- [TM that doubles a binary number](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-doubles-binary) — Theory of Computation, chapter 4
- [Pumping lemma: equal 0s and 1s](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-equal-zeros-ones) — Theory of Computation, chapter 2, asked 2×
- [TM computing f(n) = n + 1](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-increment-binary) — Theory of Computation, chapter 4
- [TM for f(w) = wwᴿ](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-f-w-wwr) — Theory of Computation, chapter 4
- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — 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

## Related in other subjects

- [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4×
- [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4×
- [Equivalence partitioning: telephone numbers](https://www.bctengineer.com/question.md?key=semester_5%2Fsoftware_engineering%3Aequivalence-partitioning) — Software Engineering, chapter 8
- [Reasons: slot numbers and speed vs size](https://www.bctengineer.com/question.md?key=semester_5%2Felectric_machine_design%3Aslot-and-speed-reasons) — Electric Machine Design, chapter 4, asked 2×