# 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?

## 1 Answer

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.

• I know what you mean, but I can't put it into effect. Could you be more specific? – 0x6B6F77616C74 Jan 11 '13 at 14:40
• 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'? – Pål GD Jan 11 '13 at 15:51
• You've guessed right. Question updated. – 0x6B6F77616C74 Jan 11 '13 at 15:56
• 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
• @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. – vonbrand Jan 27 '13 at 4:19