# GATE1997-70

3.2k views

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).

edited
1

@Arjun

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 parts.........how even final state is not given

plz explain?? (where I wrong)

0
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.
0

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

1

@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.

1

@oldDoctor

can you please briefly explain minimization procedure of this question

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

edited
0
Okay. May be misconceptions gets cleared.
0
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 ???
1

@mehul vaidya

@Verma Ashish

please explain how ABEFG and CDH are seperated

0
@amal based on output
0

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.

3

Hello @Kushagra गुप्ता ..As far as your 1st point is concerned we are Assuming that "A" is the starting state ..so 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..

0

Yes.. @Punit Sharma you are right..

0

@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] A\overset{0}{\rightarrow}$$B$

$B\overset{0}{\rightarrow}$$F A\overset{1}{\rightarrow}$$H$

$B\overset{1}{\rightarrow}$$D 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: A\overset{0}{\rightarrow}$$B$

$E\overset{0}{\rightarrow}$$D$

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

0
0
@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].
0
For anyone looking for how the partition of states is done in Po, understand that its a Mealy Machine, so there is no final state, the partitioning is done only on the basis of the outputs produced by the given states. States which are producing the same output are grouped together and after that, the normal algorithm of minimization is applied.

The states A, B, E, F, G are producing output as 1 on 0 input and the states C, D, H are producing output as 0 on the 0 input and that's how they are grouped in Po.
4

Anybody for equivalence partitioning video , start at 06:15

0
why do we need a start state? The grouping is the same even if we take G as start  state and don’t remove it.
0
Start state doesn't matter because we can not reach G from any state. So it is unreachable regardless of what we consider as the start state.
0
@kiioo we need to remove unreachable states to make the DFA as minimal as possible.
0
What if G is the start state? Then it need not be reachable by other states.

How can we say it's not the start state?
0
Ok. Your query made my understanding clearer! My first comment is incorrect.

It is essential that what is the start state. Because with each different start state the unreachable states will be different. e.g with A as start state G is unreachable and with G as start state A, B, H are unreachable. While minimizing a FA we need to remove unreachable states first. So with diff start states => diff unreachable states => diff min DFA.

In short with different start states we are looking at different DFAs altogether which would have different min DFAs.

In the question no start state is given so we are assuming the first state as the start state.
0
Yeah, that is what I was asking. When no start state is given, is it totally valid to assume the first state as the start state?
0
In almost all the questions I have solved start state has been mentioned and it should be. I think this is the problem’s fault to not mention the start state. And I dont think it is a rule to select the first state as the start state(atleast I havent read it anywhere).
We are just assuming the first one as the start state by saying “this is what questioner must be thinking while framing this question”, I think, as is the case with some of the questions in GATE where some details are omitted.
0
Okay. I too wanted to make sure that taking the first state as the start state is not a rule.

It's clear to me now. Thanks for your help:)

## Related questions

1
3.4k views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$'s is divisible by three.
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where $L^P = \left\{s \mid ss' \in L \text{ some string }s'\right\}$ $L^R = \left\{s \mid s \text{ obtained by reversing some string in }L\right\}$
Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata? $\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$ $\left\{ ww^R \mid w \in \{a,b,c\}^*\right\}$ $\left\{ a^nb^nc^n \mid n \geq 0 \right\}$ $\left\{w \mid w \text{ is a palindrome over } \left\{a,b,c\right\} \right\}$ Note: $w^R$ is the string obtained by reversing $'w'$.
Which one of the following is not decidable? Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ steps Equivalence of two given Turing machines Language accepted by a given finite state machine is not empty Language generated by a context free grammar is non-empty