I need to design a Turing Machine that accepts the (context-free) language: $L(M)=\{0^{n}1^{n+1}: n\ge1$}.

$$Q=\{q_0,q_1,q_2,q_3,q_4\} ,Σ = \{0,1\}, Γ =\{0,1,X,Y,B\}, F=\{q_4\}$$

X- processed 0
Y- processed 1
B- blank
P-move right
L-move left
So far I've succeeded to create a table for languages $\{0^n1^n\}$(without the red entry) and $\{0^n1^k:k\ge n\}$.

"P" means the right side

What should it look for case in which there is minimal superiority of "1's"?


Meanwhile I've finally hit on an idea for L(M)

enter image description hereIs it correct?


1 Answer 1


If you have managed to solve $0^n1^n$ then $q_4$ should simply proceed to the rightmost bit you haven't processed yet and verify that it's a 1 and that there is nothing following it.

  • $\begingroup$ I know what you mean, but I can't put it into effect. Could you be more specific? $\endgroup$ Jan 11, 2013 at 14:40
  • $\begingroup$ Could you quickly comment on what the semantics for X, Y and B are? I guess B is blank, X is a processed 0 and Y a processed 1? Does P mean 'move right'? $\endgroup$
    – Pål GD
    Jan 11, 2013 at 15:51
  • $\begingroup$ You've guessed right. Question updated. $\endgroup$ Jan 11, 2013 at 15:56
  • $\begingroup$ Let's say that the invariant is such that your tape looks like this: $BXXX0000YYY11111B$ (just an example). In the end, your tape must look like this: $BXXXXXXXYYYYYYY1B$. Considering this, it should be straight forward to go right of all $X$'s, all $Y$'s and then verify that the next symbol is a 1 and then a $B$. I'm not going to decode your transition table (probably no one else either) so you will have to explain your algorithm (or at least idea) in a clear and precise, yet easy to understand readable English. $\endgroup$
    – Pål GD
    Jan 11, 2013 at 17:09
  • $\begingroup$ @PålGD, totally agree. This is programming, and that is convincing your fellow humans that it works in all cases, not asking the computer to calculate a few results and concluding that if they look OK it will be OK in all cases. $\endgroup$
    – vonbrand
    Jan 27, 2013 at 4:19

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.