# Finite-state machine problem

1. Nov 16, 2009

### livcon

1. The problem statement, all variables and given/known data
Construct a finite-state machine that changes every other bit, starting with the second bit, of an input string, and leaves the other bits unchanged.

2. Relevant equations
-

3. The attempt at a solution
Say I have the string 1001101, then I am supposed to make a finite-state machine that turns it into 1100111 (every other bit changed, starting from the 2nd). I know how to change the bits in a machine, what I need help for is how to determine the index of the input, that is how to let the finite-state machine know i.e. that 0 which happens to be the second bit of the string, is in fact the second.
Thanks.

2. Nov 16, 2009

### livcon

I realized that this problem is quite easy and requires only two states, $$s_{0}$$ and $$s_{1}$$, using the first one as initial state. When the machine recieves either 0 or 1 in the initial state, the output function simply returns the same bit as the input as it changes state from $$s_{0}$$ to $$s_{1}$$. From this state the bit changes on its way back to state $$s_{0}$$.