Input alphabet: 0,1
Language: {1,11,1101,1101001,11010010001,1101001000100001,...}
Tape alphabet: 0,1,#,b (where b denotes the blank symbol)
Note that none of the transitions replace a 1 by any other symbol, or print a 1 on the tape in place of some other symbol.
| State | 0 on tape | 1 on tape | # on tape | b on tape | comment |
| i | . | δ(i,1)=(i',1,R) | . | δ(i,b)=(accept,b,R) | In initial state, accept if blank, move right if 1 (and go to state i'), reject if 0. Also rejects if # is seen. In i', accept if blank, move right if 1. States i and i' are only ever used during the first 2 steps of computation. |
| i' | . | δ(i,1)=(q,1,R) | . | δ(i,b)=(accept,b,R) | |
| q | δ(q,0)=(s',#,R) | . | . | δ(q,b)=(accept,b,R) | In state q, delete a 0, move right, get ready to delete 2 zeroes, one from each block being compared. State q corresponds to a state of the system where the TM has just compared 2 consecutive blocks of 0's, and moved to the right of the 1 to their right. |
| r | . | δ(r,1)=(r',1,L) | δ(r,#)=(r,#,L) | . | move left, looking for corresponding 0 (use 2 states r and r' to remember whether a 1 has been by-passed.) |
| r' | δ(r',0)=(s,#,R) | . | δ(r',#)=(r',#,L) | . | |
| s | . | δ(s,1)=(s',1,R) | δ(s,#)=(s,#,R) | . | move right, look for new 0 to delete (use 2 states s and s' to remember whether a 1 has been by-passed) |
| s' | δ(s',0)=(r,#,L) | δ(s',1)=(t,1,L) | δ(s',#)=(s',#,R) | . | |
| t | . | δ(t,1)=(t',1,L) | δ(t,#)=(t,#,L) | . | In states t and t', move to left, prior to replacing #'s by 0's. |
| t' | . | δ(t,1)=(u,1,R) | δ(t',#)=(t',#,L) | . | |
| u | . | δ(u,1)=(u',1,R) | δ(u,#)=(u,0,R) | . | In states u and u', move to right, replacing #'s by 0's. |
| u' | . | δ(u',1)=(q,1,R) | δ(u',#)=(u',0,R) | . |
1 1 0 1 0 0 1 0 0 0 1 ... i
1 1 0 1 0 0 1 0 0 0 1 ... i'
1 1 0 1 0 0 1 0 0 0 1 ...
q
1 1 # 1 0 0 1 0 0 0 1 ...
s'
1 1 # 1 0 0 1 0 0 0 1 ...
r2
1 1 # 1 0 0 1 0 0 0 1 ...
t
1 1 # 1 0 0 1 0 0 0 1 ... t
1 1 # 1 0 0 1 0 0 0 1 ... t'
1 1 # 1 0 0 1 0 0 0 1 ... u
1 1 # 1 0 0 1 0 0 0 1 ...
u'
1 1 0 1 0 0 1 0 0 0 1 ...
u'
1 1 0 1 0 0 1 0 0 0 1 ...
v
1 1 0 1 0 0 1 0 0 0 1 ...
q
1 1 0 1 # 0 1 0 0 0 1 ...
s'
1 1 0 1 # # 1 0 0 0 1 ...
r
1 1 0 1 # # 1 0 0 0 1 ...
r
1 1 0 1 # # 1 0 0 0 1 ...
r'
1 1 # 1 # # 1 0 0 0 1 ...
s
1 1 # 1 # # 1 0 0 0 1 ...
s'
1 1 # 1 # # 1 0 0 0 1 ...
s'
1 1 # 1 # # 1 0 0 0 1 ...
s'
1 1 # 1 # # 1 0 0 0 1 ...
t
1 1 # 1 # # 1 0 0 0 1 ...
t
1 1 # 1 # # 1 0 0 0 1 ...
t
1 1 # 1 # # 1 0 0 0 1 ...
t'
1 1 # 1 # # 1 0 0 0 1 ... t'
1 1 # 1 # # 1 0 0 0 1 ...
u
1 1 0 1 # # 1 0 0 0 1 ...
u
1 1 0 1 # # 1 0 0 0 1 ...
u'
1 1 0 1 0 # 1 0 0 0 1 ...
u'
1 1 0 1 0 0 1 0 0 0 1 ...
u'
1 1 0 1 0 0 1 0 0 0 1 ...
q
(note, we would have accepted if a blank was seen here)
1 1 0 1 0 0 1 # 0 0 1 ...
s'
1 1 0 1 0 0 1 # # 0 1 ...
r
1 1 0 1 0 0 1 # # 0 1 ...
r
1 1 0 1 0 0 1 # # 0 1 ...
r'
1 1 0 1 0 # 1 # # 0 1 ...
s
1 1 0 1 0 # 1 # # 0 1 ...
s'
1 1 0 1 0 # 1 # # 0 1 ...
s'
1 1 0 1 0 # 1 # # 0 1 ...
s'
1 1 0 1 0 # 1 # # # 1 ...
r
1 1 0 1 0 # 1 # # # 1 ...
r
1 1 0 1 0 # 1 # # # 1 ...
r
1 1 0 1 0 # 1 # # # 1 ...
r'
1 1 0 1 0 # 1 # # # 1 ...
r'
1 1 0 1 # # 1 # # # 1 ...
s
1 1 0 1 # # 1 # # # 1 ...
s
1 1 0 1 # # 1 # # # 1 ...
s'
1 1 0 1 # # 1 # # # 1 ...
s'
1 1 0 1 # # 1 # # # 1 ...
s'
1 1 0 1 # # 1 # # # 1 ...
s'
1 1 0 1 # # 1 # # # 1 ...
t
and so on...