Electronic – How to determine what the states should be in this state diagram

First design the state machine without worrying about the clk. You have to remember something about what happened with the last 3 inputs, so at worst you are going to need 8(=2^3) states (but you can do substantially better than that.)

Once you have the state diagram, you need to choose an n-bit representation for each state. You will store this in an n bit register.

Then you write down the truth table for the transition function. There will be n+1 inputs (the n-bit state, and the 1 bit for X.) There will be n output bits (representing next state.)

Then you figure out how to implement a circuit that performs the truth table.

Finally, you need to implement the output function. This will be a circuit that is true when you are in the state where the last three bits are 110, and false otherwise.

In your final circuit you will have an n-bit clocked register, and a bunch of combinational logic.

You are almost done, all what's left is to get the logic equations from the table. Remember that w is an input so it is part of the present state and we will use it to compute values of the next state.

Let w be a 2 bit number, $$w = w_1w_0$$

so if we let A = 00, B = 01, and C = 11 then:

$$ w = \left.\begin{cases} \bar{w_1} \bar{w_0} & w = A\\ \\ w_1 \bar{w_0} & w = B\\ \\ w_1 w_0 & w = C \end{cases} \right\} \\ \\ $$

and the 5 states are $$ S_i = \left. \begin{cases} \bar{y_2 }\bar{y_1 }\bar{y_0 }& i = 1 \\ \\ \bar{y_2 }\bar{y_1 } y_0 & i = 2 \\ \\ \bar{y_2 } y_1 \bar{y_0 } & i = 3 \\ \\ \bar{y_2 } y_1 y_0 & i = 4 \\ \\ y_2 \bar{y_1} \bar{y_0 } & i = 5 \end{cases} \right\} $$

To get the logic for computing the next state you get the boolean equation for each bit of the next state separately.E.g to get the logic for computing y0 :

$$ y_{0 , next} = S_1 A + S_2 A + S_3A + S_3 C + S_4 A + S_5 A $$

$$ y_{0, next} = \bar{y_2 }\bar{y_1 }\bar{y_0 } \bar{w_1} \bar{w_0} + \bar{y_2 }\bar{y_1 } y_0 \bar{w_1} \bar{w_0} + \bar{y_2 } y_1 \bar{y_0 } \bar{w_1} \bar{w_0} + \bar{y_2 } y_1 \bar{y_0 } w_1 w_0 + \bar{y_2 } y_1 y_0 \bar{w_1} \bar{w_0} + y_2 \bar{y_1} \bar{y_0 } \bar{w_1} \bar{w_0} $$

which reduces to

$$ y_{0, next} = \bar{w_1}\bar{w_0} + \bar{y_2 } y_1 \bar{y_0 } w_1 w_0 $$

Repeat this for y2 and y1, to get the rest of the combinational logic required.

The output(z) is high when this state machine is in state 5 so Z will be given by:

$$ z = S_5 = y_2 \bar{y_1} \bar{y_0 } $$

This is a moore machine as Z is only dependent on the current state.