TOC: Number of states in minimum DFA

Question

I think, there will be 4 states  in minimum DFA, following states will be merged in the resulted DFA

{q0&q3}, {q4&q5}, {q1&q6}, {q2&q7}

Comments

{q1&q6} will be seperated.  5 will be answer.

---

I am getting the following sets:

{0, 4, 5}, {3], {1, 6}, {2, 7}

---

For q₁ =  (a)q5        (b) q2

For q₆ =  (a)q3        (b) q7

here q3   and q5 are not belongs to same set so need to be seperated. 

---

5 states will be there in minimized data.

{q₀,q₄,q₅} {q₃} {q₁} {q₆} {q₂,q₇}

Answer 1

Transition Table:-

	a	b
q0	q1	q4
q1	q5	q2
*q2	q3	q6
q3	q3	q3
q4	q1	q4
q5	q1	q4
q6	q3	q7
*q7	q3	q6

$0 \ equivalent \ set$

$\left [ q0,q1,q3,q4,q5,q6 \right ] \ \ \ \left [ q2,q7 \right ]$

$1 \ equivalent \ set$

$\left [ q0,q3,q4,q5 \right ] \ \ \ \left [ q1,q6 \right ] \ \ \  \left [ q2,q7 \right ]$

$2 \ equivalent \ set$

$\left [ q0,q4,q5 \right ] \ \ \ \left [ q1,q6 \right ] \ \ \ \left [ q3 \right ] \ \ \ \left [ q2,q7 \right ]$

$3 \ equivalent \ set$

$\left [ q0,q4,q5 \right ] \ \ \ \left [ q1 \right ] \ \ \ \left [ q6\right ] \ \ \ \left [ q3 \right ] \ \ \ \left [ q2,q7 \right ]$

DFA after minimization :- 

Comments

Yes, q1 and q6 will be separated, both are not 3-equivalent. as on the input 'a' q1 and q6 are transitioning to different groups.

q6 on 'a' goes to q3

And, q1 on 'a' goes to 'q5' 

q3 and q5 don't belong to same group.

---

final Minimized state should be-:

$\left [ q_0,q_4,q_5 \right ],\left [ q_1 \right ],\left [ q_6 \right ],\left [ q_3 \right ],\left [ q_2,q_7 \right ]$

---

yes @Sourav!

Answer 2

I think answer will be {q0,q4,q5} &{q3}&{q1,q6}&{q2,q7} so number of states will be 4.

Answer 3

First, we check there are some states which are not reachable from the start state in the DFA. Here this is not the case since every state is reachable from the start state. (If there are some states which are not reachable from the start then we will remove them first)

Transition Table of the Given DFA in the question 

	a	b
q0	q1	q4
q1	q5	*q2
*q2	q3	q6
q3	q3	q3
q4	q1	q4
q5	q1	q4
q6	q3	*q7
*q7	q3	q6

Partitions are :

P0={ {q0,q1,q3,q4,q5,q6}   {q2,q7} }

P1={ {q0,q3,q4,q5} {q1,q6} {q2,q7} }

P2={ {q0,q4,q5}  {q3}  {q1,q6}  {q2,q7} }

P3={ {q0,q4,q5}  {q3}  {q1} {q6}  {q2,q7} }

P4={ {q0,q4,q5}  {q3}  {q1} {q6}  {q2,q7} }

Therefore finally we need total of 5 states in Minimal DFA.

Comments

Bro, q7 is also a final state.

---

 Rajnish Kumar 1 for your p3 (q1->a=q5) and (q6->a=q3) which is in different state so q1 and q6 are 2 different states so 5 states in MDF

---

@ Hira Thakur & Rishabh

Thank's for pointing out the mistake now edited.