# Enumerator for $L=\{0^{3^n}| n\ge 0\}$

I need to build an enumerator for $$L=\{0^{3^n}| n\ge 0\}, \Sigma = \{0\}, \Gamma = \{0, x, \sqcup\}$$ that has at most 10 states, including print and halt states. I can ignore the halt state and any edge that leads towards it.

I tried to approach this in the simplest way i could think of, build a Turing machine that decides $$L$$ and then build an enumerator around it, and this is the result

the states are:

• I - initializing state, puts a blank, $$\sqcup$$, at the start of the tape
• q0 - starts a division by 3
• q1 - checks if we reach a single 0 if so print else continue with division by crossing a single 0
• q2 - cross first/second 0 for division if there is none, i.e not divisible by 3, add 0 to tape and rewind
• q3 - check if divisible by 3, if so rewind to check again, else continue with division
• q4 - continue with division by crossing first 0 if there is none, i.e not divisible by 3, add 0 to tape and rewind
• rw - rewind to start of tape at the end of successful division
• rr - rewind to start of tape following addition of a single 0, replacing x with 0 to check again if the input length is a power of 3
• rnp - rewind to start of tape following successful run of the Turing machine, replacing x with 0, and for each symbol, 0 or x, put 0 in output
• print - prints output and start a new run of the Turing machine

But I have 2 problems I would appreciate help with:

1. I have 11 states, and I need no more than 10. Is there a way to simplify my existing machine?
2. The question says at most 10 states, thus I assume there might be an even simpler machine I can describe, yet after several days working on this, I'm just unable to find anything

I think I found an answer to my first question by sort of splitting $$q0$$, merging half of it into $$q1$$ and merging the $$I$$ state into the rest of it

In the new machine, I use the blank, $$\sqcup$$, at the start of the tape to mark the first 0 (the empty word isn't part of $$L$$ so I can ignore the case $$q0$$ came to handle in the first machine), and the move from $$q1$$ to $$rnp$$ also puts a 0 in the output to compensate for the missing 0 at the start.

The machine now has 10 states (including halt state) which is what was required