search
Log In
0 votes
91 views

After  minimzing, only 4 states left then why 6 ?

in Theory of Computation 91 views
0

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

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

{{q3},{q5}{q1,q2},{q0,q4}{q0,q3,q4},{0,3,4,5}}

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

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

Related questions

2 votes
3 answers
1
463 views
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language? $4$ $16$ $20$ $24$
asked May 22, 2019 in Theory of Computation Hirak 463 views
0 votes
0 answers
2
185 views
For an DFA having exactly 2 a’s and more than 3 b’s what is the minimum number of states???
asked Apr 7, 2019 in Theory of Computation Doraemon 185 views
2 votes
1 answer
3
398 views
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything? answer is 20 or 64?
asked Mar 24, 2019 in Theory of Computation aditi19 398 views
...