0
\$\begingroup\$

I have been asked to show 2 Finite State Machines are equivalent by computing the product machine of both. Below is an image of 2 transition tables corresponding to 2 Finite State Machines.

How do I construct the product machine of both of them?

2 FSMs

Both FSMs have an initial state of A. So my understanding is you start at A and feed an input of 0 and see where both machines take you. In this case, starting at A with input of 0 takes you to D for the left transition table and outputs 0. Starting at A with input of 0 takes you to B for the right transition table and outputs 0. Isn't this a counter-example immediately (i.e. both of these FSMs are not equivalent)?

But for some reason the problem is stated in such a way that I need to prove they are equivalent. So I"m a little confused, is the problem stated incorrectly or are these two machines really equivalent?

\$\endgroup\$
  • \$\begingroup\$ Draw some transition graph. Then try converting the machines to regular expressions. Might be easier to see then whether the machines are equivalent (i.e. accept exactly the same language (set of strings of 0's and 1's)). You can do a kind of algebra on regexes which can help to show equivalence. For instance a?a* reduces to just a*. \$\endgroup\$ – Kaz Dec 9 '12 at 0:26
  • \$\begingroup\$ The outputs are the same, so it's not a counterexample. That the internal state is different doesn't matter. \$\endgroup\$ – starblue Dec 9 '12 at 11:41
3
\$\begingroup\$

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$$

\$\endgroup\$
  • \$\begingroup\$ Such a good book referenced highly recommend it. \$\endgroup\$ – Dean Dec 9 '12 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.