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?


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$ – 0x6B6F77616C74 Jan 11 '13 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 '13 at 15:51
  • $\begingroup$ You've guessed right. Question updated. $\endgroup$ – 0x6B6F77616C74 Jan 11 '13 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 '13 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 '13 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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