3.7k 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$
edited | 3.7k views

Answer is (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

edited 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

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.

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)

edited

@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
–1 vote
Option D is correct as LCM of 6 and 8 is 24, also 48 is a multiple of 24 .
how LCM helps?

No need to even thnk about lcm..its simply multiplication refer the example in the image

Please tell me the book name
You are referring to
someone plz atleast mention the book or source for these type of questions, i can't find this concept in peter linz