[DTM] Increment bit-string / Overflow handled

// Input: a binary number n, for example 1101
// Ouput: 01101
//
// Author: Milan Nedic
//

name: Increment bit-string (handles overflow)
init: to_the_right
accept: qAccept

to_the_right,0
to_the_right,0,>

to_the_right,1
to_the_right,1,>

// to_the_right takes me to the first empty position on the right

// empty found? put the placeholder
// and get back one place
to_the_right, _
to_the_left, x, <

// move back through all placeholders
to_the_left, x
to_the_left, x, <

// you saw 0 while moving back?
// bring it forward one place
to_the_left, 0
bring_0, x, >

bring_0, 0
bring_0, x, >

bring_0, x
to_the_left, 0, <

// ---------------------
// you saw 1 while moving back?
// bring it forward one place
to_the_left, 1
bring_1, x, >

bring_1, 1
bring_1, x, >

bring_1, x
to_the_left, 1, <

to_the_left,_
clear_placeholder,_, >

clear_placeholder, x
init_incr, 0, >

// increment initialization, move
// to the end again.
init_incr, 0
init_incr, 0, >

init_incr, 1
init_incr, 1, >

init_incr, _
increment_lsb, _, <

// if prior to incr you read 0 on LSB bit
// you simply add 1 and the process is done.
// go to the left.
increment_lsb, 0
incr_done, 1, <

incr_done, 0
incr_done, 0, <

incr_done, 1
incr_done, 1, <

incr_done, _
dAccept, _,-


// if you land on 1, then you increment it
// and carry 1, so the zero is printed
increment_lsb, 1
carry_1, 0, <

carry_1, 0
incr_done, 1, <

carry_1, 1
carry_1, 0, <