12,764 views

Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have?

1. $8$
2. $14$
3. $15$
4. $48$

### Subscribe to GO Classes for GATE CSE 2022

Correct Option: D

It can be proved using Myhill Nerode theorem. We need a separate state for $\#a \ mod \ 6 = 0..5$ and $\#b \ mod \ 8 = 0..7$. Each combination of them must also be a new state giving $6*8 = 48$ minimum states required in the DFA.

Reading Myhill-Nerode theorem might be confusing though it is actually very simple.

http://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf

by

what would be an answer if I change the given condition to "number of a's divisible by 6 or number of b's divisible by 8"
same 48 states ..no of final states increased and .. if they asked for same symbol then we have to take lcm

if they asked for same symbol then we have to take lcm

explain this  sid1221

We can take Cartesian product of given two dfas M1 & M2, accepting the languages L1 and L2 respectively where:

L1={w over Σ={a,b} accepting all strings which have number of a's divisible by 6}, say has 'm' states

L2={w over Σ={a,b} accepting all strings which have number of b's divisible by 8}, say has 'n' states

Step 1: Take Cartesian product and create a dfa M with m*n # of states. (total # of states)

Step 2: The difference of AND/OR comes on basis of selection of final states in M..

If OR(means UNION) so in M choose all states as final states wherever final states of EITHER M1 or M2 occurs..

If AND(means INTERSECTION) so in M choose all states as final states wherever final states of BOTH M1 and M2 occurs..

So by question, M1 has 6 states, M2 has 8 states. Final dfa has 6*8=48 states.(only total # of states is asked here and it will be minimum).

Please correct me if I am wrong.
Can't this be done in 24 states as mod 8 dfa can be done in 4 states(since minimum is asked) and mod 6 in 6 states. So, 6x4 -> 24 states. Is 24 not considered because it's not in option .Is it the case ?
@Spandan, how mod 8 dfa can be done in 4 states?
edited

In case if the question had been given as " number of a's divisible by 6 and number of a's divisible by 8" then the number of states would be 24 and if given as " number of a's divisible by 6 but not divisible by 8 " then the number of states would be 24 right?

Moreover if it is given as " number of a's divisible by 6 and number of b's divisible by 12 " (or) " number of a's divisible by 6 or number of b's divisible by 12 " (or) " number of a's divisible by 6 but not  number of b’s divisible by 12 " then it would be 72 states right?

@Shivateja MST yes absolutely correct.

1. For different symbols – no. of a’s is divisible by x and no. of b’s is divisible by y, we will have xy states.
2. For same symbols – no. of a’s is divisible by x and no. of a’s is divisible by y, we will have lcm(x,y) states.

Instead of “and” there can be any logical operation (or, but not etc) but the no of states will still remain the same, only the set of final states will change.

But vaibhav, I think you can do a little more generalisation.

It is ok to say LCM(x,y)

now it does not matter, x,y are same or not.

it will always give correct answer.
No. In fact if we do that then the answer to this question should be 24, but 48 is the correct answer
yes you are correct.
Answer is D: 6 states for a's and 8 states for b's, and condition is AND so number of states will be 6X8 = 48 states.

if the condition would have been OR, then the min dfa will contain 14 or 15 states ?
what about OR case?? can anybody give the right solution?
OR does not make a difference in this question - just some more states become final.
For 'OR' case, we have either a is divisible by 6 or b is by 8. Total #states = 48 as in 'AND' case.

Only final states will be more. We will count final states like (0,x) and (x, 0) where x E [0,5] for 'a' and [0,7] for 'b'.

For 'a' we have 6 such final states, for 'b' we have 8.

Total 6 + 8 - 1 = 13 final states as we have counted state (0,0) twice.

I will give a short trick for divisibility: |w| i.e length of string is divisible by a,b.

If a doesn't divide b and b doesn't divide a then Min. states = a*b

Case 1 : Divisible by a and b ----> If a divides b or b divides a then Min. No .of states = LCM(a,b)
Case 2: Divisible by a or b  ------> If a divides b or b divides a then Min. states =  GCD(a,b)

@amitabh, you are wrong in case of Divisible by a or b , for example just check divisible by 2 or 3 and we  require atleast 6 states in min. dfa but your answer gives GCD(2,3) = 1

Pls check for your multiplication part too.as i am not sure though.

Edited

anyone verify this"

I will give a short trick for divisibility: |w| i.e length of string is divisible by a,b.

If a doesn't divide b and b doesn't divide a then Min. states = a*b

Case 1 : Divisible by a and b ----> If a divides b or b divides a then Min. No .of states = LCM(a,b)
Case 2: Divisible by a or b  ------> If a divides b or b divides a then Min. states =  GCD(a,b)

"

Can you please mention the source or the authenticity of this, my friend.
never apply these rule...fjust ollow properties
Option D is correct as LCM of 6 and 8 is 24, also 48 is a multiple of 24 .
by

how LCM helps?
someone plz atleast mention the book or source for these type of questions, i can't find this concept in peter linz