1,610 views

2 Answers

Best answer
8 votes
8 votes

Let every state be represented as $(n_a(w)mod\;3,n_b(w)mod\;2)$, then the DFA will look like :

And clearly it contains $5$ final states. Drawing DFA is not necessary as we could form all $6$ possibilities of  $\left ( \bf{\color{blue}{n_a(w)mod\;3}},\bf{\color{red}{n_b(w)mod\;2}} \right )$ which are $\big \{\bf {\color{blue}{0}}{\color{red}{0}},{\color{blue}{0}}{\color{red}{1}},{\color{blue}{1}}{\color{red}{0}},{\color{blue}{1}}{\color{red}{1}},{\color{blue}{2}}{\color{red}{0}},{\color{blue}{2}}{\color{red}{1}} \big\}$  and each of these is a state in the DFA and look among these $6$ states that how many states satisfy constraint $n_a(w) mod\;3 \ge n_b(w) mod\;2$.

edited by
3 votes
3 votes

If we draw DFA of  L = {na(w)mod 3  &&  nb(w) mod 2 }.

minimum number of states = 6 = {00,01,10,11,20,21}; these are residue of a,3 and b,2 respectively 

So only one state where we will get na(w)mod 3  <  nb(w) mod 2,

So Answer should be 6-1= 5.

Related questions

5 votes
5 votes
3 answers
1
Manu Thakur asked Oct 9, 2017
2,136 views
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}
1 votes
1 votes
1 answer
2
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!
2 votes
2 votes
2 answers
3
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...
0 votes
0 votes
1 answer
4