The FSM (Finite State Machine) machine pictured in the figure above

Read the input string least-significant-bit (LSB) first and treat the two right-hand states as a serial 'add 1' (increment) circuit, where one path means a carry is still pending and the other means the carry has already been absorbed.

Starting in the initial state we are adding 1, so a carry is pending. On the first input bit 0 the machine outputs 1 (0+1 = 1, carry resolved) and moves to the carry-absorbed (copy) state; on the first input bit 1 it outputs 0 (1+1 = 10, write 0, carry out) and stays on the carry-pending path.

On the carry-pending path each further input 1 outputs 0 and keeps the carry (a run of trailing 1s all become 0); the first input 0 outputs 1 and the carry is absorbed, after which every remaining bit is copied through unchanged.

Worked example (LSB first): input 0,1,1 represents 110 = 6. The machine emits 1,1,1 which reads back as 111 = 7 = 6 + 1. Input 1,1,1 = 7 emits 0,0,0 = 0, i.e. 7 + 1 with overflow. In every case the output equals the input increased by one.

Therefore the finite state machine increments the given bit pattern by 1.