2,136 views
5 votes
5 votes

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}

3 Answers

Best answer
2 votes
2 votes

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

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

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.

edited by

Related questions

2 votes
2 votes
2 answers
1
Utk asked Jan 13, 2016
16,114 views
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$I draw the following DFA The minimum number of states is 4. The answer giv...
2 votes
2 votes
1 answer
2
rahul sharma 5 asked Nov 9, 2017
938 views
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}
1 votes
1 votes
1 answer
3
Prajwal Bhat asked Jan 17, 2017
1,328 views
No. of states in the DFA accepting the following set of strings are:( ( aa* + φ* )* (aa* + φ* ) + bb* + φ* φ + φ* )*Quite confusing to me. Share your approach!
3 votes
3 votes
2 answers
4
Lokesh . asked Jan 10, 2017
1,610 views
Number of final states in minimal DFA where $\sum = \{ a,b \}$$L = \{ w| n_a(w)mod\ 3 \geq n_b(w)mod\ 2\}$