Design a Turing Machine which accepts word with odd length with one in the middle

Question

Design a Turing Machine which accepts word with odd length with one in the middle

for example : $00100\in L,\quad 011\in L$ but $101,11,11011\notin L$

I tried this:

delete the first digit(deleted digit marked with x) and then go right till you see a space, when you walk on the first space (the end of the word) delete the first digit from the right (marked with y) then go left till you see x (loop)

any ideas?

Answer 1

Your strategy of replacing with x's on the left and y's on the right is fine, but at some point you need to check for that 1 in the middle (and oddness).

So: when you get back to q0 coming from q3, and you see a y, then you must have had an even length string, so then you should reject.

Also: coming from q0: if you see a 0 you should go to a different state than if you see a 1, because that 0 or 1 could be the middle symbol. So: if after replacing that 0 or 1 with an x, and you see a y (or a space, in case your string was just a single symbol) to the right of it, then you should stop, and accept or reject depending whether you just replaced a 1 or 0 (this is why you need two different states.

Here is an updated machine: