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

4 Answers

+31 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

by Veteran (421k points)
edited by
+2
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"
+7
same 48 states ..no of final states increased and .. if they asked for same symbol then we have to take lcm
0

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

explain this  sid1221

+1
+3
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.
0
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 ?
0
@Spandan, how mod 8 dfa can be done in 4 states?
+17 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.
by Boss (13.4k points)
0
I found answer as c).....can someone please explain....
0
if the condition would have been OR, then the min dfa will contain 14 or 15 states ?
+1
what about OR case?? can anybody give the right solution?
+8
OR does not make a difference in this question - just some more states become final.
+3
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.
+3 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)

by Active (2.9k points)
edited by
+2

@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.

0
Edited
0

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)

"

0
Can you please mention the source or the authenticity of this, my friend.
0
never apply these rule...fjust ollow properties
–2 votes
Option D is correct as LCM of 6 and 8 is 24, also 48 is a multiple of 24 .
by Active (2.4k points)
+3
how LCM helps?
+3

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

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

Related questions

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
50,376 questions
55,840 answers
192,571 comments
91,401 users