GATE CSE 1997 | Question: 70

Question

GATE CSE 1997 | Question: 70

go_editor asked Oct 14, 2015 • edited Apr 14, 2019 by Pooja Khatri

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

Find the equivalence partition on the states of the machine.
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).

go_editor asked Oct 14, 2015 • edited Apr 14, 2019 by Pooja Khatri

go_editor

7.9k views

See all

Show 2 previous comments

2 Answers

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

VS answered Aug 9, 2017 • edited Apr 15, 2019 by akash.dinkar12

VS

See all

Punit Sharma

commented Dec 2, 2019

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

KUSHAGRA गुप्ता

commented Dec 3, 2019

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

nvs16

commented Oct 17, 2020

i

edited

by nvs16 Oct 17, 2020

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.

See all

Related questions

14.3k

views

1 answers

24 votes

Kathleen asked Sep 29, 2014

14,275 views

GATE CSE 1997 | Question: 20

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

Kathleen

14.3k views

Kathleen asked Sep 29, 2014

6.6k

views

4 answers

25 votes

Kathleen asked Sep 29, 2014

6,572 views

GATE CSE 1997 | Question: 11

Consider the grammar$S \rightarrow bSe$$S \rightarrow PQR$$P \rightarrow bPc$$P \rightarrow \varepsilon$$Q \rightarrow cQd$$Q \rightarrow \varepsilon$$R \rightarrow dRe...

Kathleen

6.6k views

Kathleen asked Sep 29, 2014

3.3k

views

1 answers

13 votes

go_editor asked Feb 8, 2018

3,261 views

GATE CSE 1997 | Question: 76-b

Consider the following relational database schema:EMP (eno name, age)PROJ (pno name)INVOLVED (eno, pno)EMP contains information about employees. PROJ about projects and i...

go_editor

3.3k views

go_editor asked Feb 8, 2018

6.2k

views

3 answers

12 votes

go_editor asked Oct 15, 2015

6,206 views

GATE CSE 1997 | Question: 76-a

Consider the following relational database schema:EMP (eno name, age)PROJ (pno name)INVOLVED (eno, pno)EMP contains information about employees. PROJ about projects and i...

go_editor

6.2k views

go_editor asked Oct 15, 2015

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

https://youtu.be/IXORIs1dHs0 — Amal, Aug 6, 2019
@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. — oldDoctor, Aug 7, 2019
@oldDoctor

can you please briefly explain minimization procedure of this question — Amal, Aug 7, 2019
@Bikram sir before minimization we should remove the non reachable states ..so state G should be removed?? — gari, Aug 10, 2017
@ gari

then how it looks like ? can u draw the table then ? — Bikram, Aug 10, 2017
@gari

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 — VS, Aug 10, 2017
@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 state...so should we not consider the first state in the table as the start state by default?? — gari, Aug 10, 2017
@gari we are not given any start state...so 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 :) — VS, Aug 10, 2017
@ gari

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, Aug 11, 2017
Thanks @Bikram sir for your fast response :)

Thanks @VS for the swift updation :) — gari, Aug 11, 2017
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. — mehul vaidya, Sep 5, 2018
Can any one explain how ABEFG and CDH are seperated in initial partition?where as initial and final states are not given.. — Verma Ashish, Sep 6, 2018
@mehul , @ashishPlease see the above youtube video (At the top). — Abhishek Gupta 1, Oct 19, 2018
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 ??? — Shubham Aggarwal, Dec 1, 2018
@mehul vaidya

@Verma Ashish

please explain how ABEFG and CDH are seperated — Amal, Aug 10, 2019
@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. — KUSHAGRA गुप्ता, Dec 2, 2019
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.. — Punit Sharma, Dec 2, 2019
@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.....$ — KUSHAGRA गुप्ता, Dec 3, 2019
@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]. — Raas Star, Dec 23, 2019
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. — Rijul, Apr 26, 2020
Anybody for equivalence partitioning video , start at 06:15

https://www.youtube.com/watch?v=8G3ekO8WPw0 — Adarsh Pandey, Jun 22, 2020
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. — kiioo, Oct 15, 2020
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. — nvs16, Oct 17, 2020
@kiioo we need to remove unreachable states to make the DFA as minimal as possible. — nvs16, Oct 17, 2020
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? — kiioo, Oct 17, 2020
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. — nvs16, Oct 17, 2020
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? — kiioo, Oct 17, 2020
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. — nvs16, Oct 17, 2020
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:) — kiioo, Oct 17, 2020
@Punit Sharma & @VS Thanks for the amazing explanation and solution :) — Abhrajyoti00, Oct 19, 2022

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

GATE CSE 1997 | Question: 70

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

Please log in or register to add a comment.

Please log in or register to add a comment.

Related questions

5 5 Comments reply

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

32 32 Comments reply

Please log in or register to add a comment.

1 1 comment reply

Please log in or register to add a comment.

Related questions

5 5 Comments

32 32 Comments

1 1 comment