The Gateway to Computer Science Excellence
+14 votes

Following is a state table for time finite state machine.

$$\begin{array}{|l|ll|}\hline \textbf{Present State}  &  \textbf{Next State Output}  \\ & \textbf{Input- 0} &  \textbf{Input-1} \\\hline  \text{A} & \text{B.1} & \text{H.1} \\  \text{B} & \text{F.1} & \text{D.1} \\ \text{C} & \text{D.0} & \text{E.1} \\ \text{D} & \text{C.0} & \text{F.1} \\ \text{E} & \text{D.1} & \text{C.1} \\ \text{F} & \text{C.1} & \text{C.1} \\ \text{G} & \text{C.1} & \text{D.1} \\ \text{H} & \text{C.0} & \text{A.1} \\\hline \end{array}$$

  1. Find the equivalence partition on the states of the machine.

  2. Give the state table for the minimal machine. (Use appropriate names for the equivalent states. For example if states $X$ and $Y$ are equivalent then use $XY$ as the name for the equivalent state in the minimal machine).

in Theory of Computation by Veteran (106k points)
edited by | 1.7k views


sir,  #my question

1.  In this question no starting state and final state is given

2.  in the Best answer,  how equivalance -0  is seperated in two even final state is not given

  plz explain?? (where I wrong)

Since it is a mealy machine, there won't be any final state. Also P0 is meaningless here. Start from P1 and compute the partition classes by comparing the output values generated on various inputs by the various states.

@oldDoctor 1st partition class based on output and rest based on input ??? How is that?.


@Amal I didn't understand. Pl elaborate. In this video however, elimination of redundant states is shown but I don't think we can eliminate all the redundant states using this method. Infact you can't even apply this method in this question. 



can you please briefly explain minimization procedure of this question

1 Answer

+17 votes
Best answer

As nothing is mentioned in question, assuming that the first state itself is the start state i.e. State $A$  so, State $G$ is not reachable from the start and hence is removed before applying the minimization algorithm.

  • $P0 \rightarrow [ABEFG] [CDH] \rightarrow [ABEF] [CDH]$
  • $P1 \rightarrow [AB] [EF] [CDH]$
  • $P2 \rightarrow [A] [B]  [EF] [CD] [H]$
  • $P3 \rightarrow [A] [B]  [EF] [CD] [H]$ 
    //$P2==P3$ So, stop

State table for the minimal machine ::

$$\begin{array}{|l|l|l|} \hline \text{Present State} & \text{input = 0} & \text{input = 1} \\\hline \text{A} & \text{B.1} & \text{H.1} \\\hline \text{B} & \text{EF.1} & \text{CD.1} \\\hline \text{CD} & \text{CD.0} & \text{EF.1} \\\hline \text{EF} & \text{CD.1} & \text{CD.1} \\\hline \text{H} & \text{CD.0} & \text{A.1} \\\hline \end{array}$$

by Boss (10.9k points)
edited by
@Bikram sir before minimization we should remove the non reachable states state G should be removed??


then how it looks like ? can u draw the table then ?


First of all, we are not given any starting state so we cannot conclude that G is reachable or not.

I mean eg G is itself the starting state.

And if considering the case that G is not the starting state,then We can remove G before minimization.

@Bikram sir please confirm
@Bikram sir the table is the same ....where ever G  is included we remove it in the table if minimization is adopted.

@VS we are not given any start should we not consider the first state in the table as the start state by default??
@gari we are not given any start should we not consider the first state in the table as the start state by default?

Any reference for this?
AFAIK I haven't studied something like this anywhere.If you have any reference for your claim you provide it :)


i think what you are  saying is correct .. in question no start state is mention , that means given first state in table is only start state by intuition .

@Bikram sir

Ans updated
Thanks @Bikram sir for your fast response :)

Thanks @VS for the swift updation :)
Hi vidhi

can you please explain why did you took CDH in one set in p0 itself

I have studied algorithm

P0 should be like [all non final reachable state] [all final reachable states]

and in [all final reachable states]  only H should be there.
Can any one explain how ABEFG and CDH are seperated in initial partition?where as initial and final states are not given..
@mehul , @ashishPlease see the above youtube video (At the top).
Okay. May be misconceptions gets cleared.
a small doubt in final table from [EF] to input 1 it should be CC but here it is CD.  

same for H to input 0 can you explain ???

@mehul vaidya

@Verma Ashish

please explain how ABEFG and CDH are seperated

@amal based on output

@Punit Sharma @Verma Ashish

Initially they are separating based on output which can be seen from the figure.

My question is that:

1. How we are finding out that G is not reachable ?

2. After separating them in P0, how we are separating [AB] in one set and [EF] in another in P1 and similarly in P2 & P3.

Any kind of help would be nice.


Hello @Kushagra गुप्ता ..As far as your 1st point is concerned we are Assuming that "A" is the starting state from "A" the State G is not reachable ...If a state is not reachable from initial state then its sense less to include in Automaton as its of no use...
Now..fist we partioned them based on Output as to merge states or reduce redundant states ..we can merge only those states which have same output...after that usual state reduction algo. is followed from P1 onwards means, we are checking for 1st equivalent (means string of length 1 reaching to same destination state)  then 2-Equiv. (strings of length 2)  and so on....the procedure to do that is to compare for every pair of two states which are in same set see on both input symbols there destination belongs to same set,if they belong to same set then in next partition keep them in same set otherwise create another.. same way repeating until getting no change in two succesive..


Yes.. @Punit Sharma you are right..


@Punit Sharma

$+1$ Thanks man.

One more thing is it a procedure in $mealy/moore$ that initially we have to separate them based on $output$ only and not on any other thing $?$

$Set\ 1:\ [ABEF]$$[CDH]$






$B\ \&\ F$ same set on input 0 and $H\ \&\ D$ same set on input 1. Hence $AB$ will be in same set.

We can observe $E$ either with $A\ or\ B$ as both are in same set, and we found out that E will not be in the set with $AB$ because:



$B\ \&\ D$ are on different sets. Hence $A\ \&\ E$ will be in different sets and $So\ on.....$

@Kushagra ,@Punit Sharma, How can you say that output associated with H is 0. even if we convert it into Moore then op associated with H is 1.(Since when nextstate is H then op is 1). Plz help guys ,not getting how partition in P0 written [CDH].

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,395 answers
105,446 users