The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
3.3k 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
asked in Theory of Computation by Veteran (68.8k points)
edited by | 3.3k views

4 Answers

+23 votes
Best answer

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

answered by Veteran (332k points)
selected 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

+15 votes
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.
answered by Veteran (13.8k points)
I found answer as c).....can someone please explain....
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.
+4 votes

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)

answered by Loyal (2.8k points)
edited by

@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 .
answered by Loyal (2.6k points)
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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,330 questions
39,146 answers
108,247 comments
36,501 users