Finite state machine (FSM) that controls a memory block

The easiest way to prove that two FSM's are equivalent is to minimize both and see if the results are the same.

To do this, you can use the partitioning minimization procedure as explained in section 8.6.1 of Fundamentals of Digital Logic.

Without going into too much detail, I will illustrate this procedure for your left state machine. The idea is to partition all states in such a way that states in the same partition are equivalent.

We start by assuming that all states may be equivalent by partitioning the states into one partition. Before doing this, note that states B and F are unreachable and can be deleted from the FSM. Therefore, the first partition is as follows:

$$P_1 = (ACDE)$$

The next step is to create groups of states with the same output value. This gives the following partition:

$$P_2 = (ACE)(D)$$

Next, we have to make sure that all the 0-successors of the states in a group are contained in one group (the same holds for the 1-successors). For example, the 0-successors of (ACE) are (DAA) which are not contained in a single group. Therefore, the group (ACE) needs to be split:

$$P_3 = (A)(CE)(D)$$

Since both the 0-successors (AA) and the 1-successors (EC) of (CE) are contained within one group, this partition does not need to be split anymore. This final partition learns us that states C and E are equivalent and we need three states in the minimal FSM.

Now we can introduce names for the new states: S1 = (A), S2 = (CE) and S3 = (D) and construct a new state table:

-------------------------
Current Next state Output
State     0    1
-------------------------
S1        S3   S2     0
S2        S1   S2     0
S3        S2   S1     1
-------------------------

Doing the same for your right state machine gives the following partition: $$P = (ACE)(D)(BF)$$

Using the state assignment S1 = (ACE), S2 = (D) and S3 = (BF) gives exactly the same state table as above. Hence, the two state machines are equivalent.

$$\blacksquare$$

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.