The Gateway to Computer Science Excellence
0 votes

After  minimzing, only 4 states left then why 6 ?

in Theory of Computation by Active (5.1k points) | 54 views

i'm getting [q0,q3,q4],[q5],[q1,q2] as 3 states plz verify it, how set [q0,q3,q4]  will partition into 2 groups?? 

yes there are four states but in the question he is asking the different sets not the states so after minimization six different sets would be there & they are :


read the question carefully.
i'm just asking for MDFA containing how many states??
@Raghav Khajuria

Yeah, thanks.
I got confused when I read Myhill- Nerode because then i thought of equivalence class.

What would be the answer if they ask for equivalence classes for given FA.
Will it be 4 as its MDFA has 4 states ?

Or, Myhill - Nerode itselt is applied on MDFA only ?
@Hira Thakur


4 states. Look in the given solution. The already applied minimisation.

$q_3$ has a separate partition as $q_3$ on $a$ is going to $q_5$ which is a different partition hence $q_3$ is not equivalent to $q_0$ and $q_4$.

1 Answer

+1 vote
In the question, they aren't asking about the number of minimal states but they are asking distinct sets, that were observed in the minimization process.So it is 6.
by Active (2.3k points)
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,741 questions
57,251 answers
104,693 users