1
$\begingroup$

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 resultenter image description here

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
$\endgroup$

1 Answer 1

1
$\begingroup$

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 itenter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.