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$$
Your state diagram has a number of errors so you need to fix those before you try to actually implement the machine. For example, from S0 you have two transitions labeled 0,0 and from S1 you have two transitions labeled 1,0. Carefully check all of the states and all of their transitions. There's no point in going any further until you have a correct specification for the machine.
Best Answer
I like these problems. They're like Sudoku for EEs.
I am not familiar with your style of Karnaugh-map. I will show you how we were taught this.
The state register has two flip-flops with inputs D1, D0 and outputs Q1, Q0. We have inputs TC, C7 and RESET. Reset is a special case. If we want it to be asynchronous then we connect it to the reset input of the flip-flops, and then it does not enter into our logic equations. If we want it to be synchronous then we do use it in the equations, but its function is so simple that we can keep it out of the K-maps.
First we will deal with the state transitions, then with the outputs.
D1 and D0 get their own K-maps. Reset is 'R' and you can eliminate it if we're to use asynchronous resets.
Now the outputs. Since the outputs only depend on the state values and not the inputs (name that state machine), it makes it easy to write the output equations by inspection.
WALK is only on in state 00.
WALK = !Q1 * !Q0
(! means 'not')HAND is on in states 11 and 10.
HAND = Q1
NUM_ON is on in states 01 and 11.
Num_on = Q0
Finally EN is only off in state 01.
EN = !( !Q1 * Q0)