- 2073 Shrawan
TM for equal numbers of x, y, z
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.
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#.
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)
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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- TM that doubles a binary number · Theory of Computation, chapter 4
- Pumping lemma: equal 0s and 1s · Theory of Computation, chapter 2 · asked 2×
- TM computing f(n) = n + 1 · Theory of Computation, chapter 4
- TM for f(w) = wwᴿ · Theory of Computation, chapter 4
- TM accepting wwᴿ; process 101101 · Theory of Computation, chapter 4
- TM configuration; TM for palindromes · Theory of Computation, chapter 4
- Design FSA accepting even number of a's · Discrete Structure, chapter 2 · asked 4×
- Design FSA accepting odd number of b's · Discrete Structure, chapter 2 · asked 4×
- Equivalence partitioning: telephone numbers · Software Engineering, chapter 8
- Reasons: slot numbers and speed vs size · Electric Machine Design, chapter 4 · asked 2×