Construct a Turing Machine that recognizes the set $\{0^{2n}1^n|n\geq 0\}$

Question

The full question is: Construct a Turing machine that recognizes the set $\{0^{2n}1^n \mid n\geq 0\}$. The Turing machine starts with the input on the tape and the head over the leftmost symbol of the input. The symbols to the left of the input are blanks out to infinity, as are the symbols to the right of the input. If the string is accepted, the machine should halt with 1 on the tape (the rest of the tape should be blank). If the string is rejected, the machine should halt with 0 on the tape.

Yes, this is a homework question, but I think I just need some help understanding the problem. We have not gone very in depth into Turing Machines, and he suggested we should just write the answer graphically like a Deterministic Finite State Machine with read, write, and direction in the transitions.

I am getting stuck because I can only think about it in terms of 3 different paths (being 001, 100, 010), but I know this is most likely not correct, and I do not know how to recognize if the string is not in the set. I understand that the machine know the string has ended when it reads a blank, and then it will move right one and write either a 1 or 0 depending on if the string is accepted or not, but I can only think about it as 3 different paths.

Help would be appreciated! Thanks!

Answer 1

Here is a Turing machine on the online simulator I found here.

name: Recongnize 0^2n 1^n
init: s0
accept: acc

s0, 0
s1, _, >

s1, 0
s2, _, >

s2, 0
s2, 0, >

s2, 1
s2, 1, >

s2, _
s3, _, <

s3, 1
s4, _, <

s4, 0
s4, 0, <

s4, 1
s4, 1, <

s4, _
s0, _, >

s0, _
acc, _, -

The idea is to delete the two zeroes on the left, got to the end on the right, delete one, go to the way to the left, repeat. Accept only when after deleting 1 on the right the tape is empty.

Answer 2

You have two main steps. You first have to verify that the input is in the language. If so, erase it all and write a $1$, otherwise erase it all and write a $0$. I'm assuming the input alphabet is $\left\{0,1\right\}$ and the tape alphabet is $\left\{0,1,x,␣\right\}$.

Roughly, you're going to want to pair up the first half of $0$s with $1$s, by crossing off a $0$ then a $1$ with $x$s, moving the tape head back and forth across the tape, until you run out of $1$s. If you run out of $0$s to cross off before $1$s, you should reject since there's less $0$s than $1$s.

Then you should pair up the rest of the $0$s with the crossed off $1$s, crossing and uncrossing them respectively, one at a time, moving back and forth like before. If you run out of $0$s to cross off before uncrossing all of the $1$s, you have less than twice as many $0$s as $1$s, so reject. If you uncross the rest of the $1$s before crossing off the rest of the $0$s, you have more than twice as many $0$s as $1$s.

If you end up crossing off the rest of the $0$s along with uncrossing all of the $1$s, you have twice as many $0$s as $1$s and should accept, but first you need to clear the tape and write your output. If you have already rejected, do the same.

After you have constructed a TM, I highly urge you to test it with varying inputs, like $\epsilon$, $0$, $1$, $10$, $01$, $001$, $0010$ to verify it's accepting and rejecting the appropriate inputs.