# Design the transition function

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\}$. What should it look for case in which there is minimal superiority of "1's"?

@EDIT

Meanwhile I've finally hit on an idea for L(M) Is 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.
• 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. – Pål GD Jan 11 '13 at 17:09