in Theory of Computation edited by
18,380 views
41 votes
41 votes

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 edited by
18.4k views

4 Answers

54 votes
54 votes
Best answer

Correct Option: D

It can be proved using Myhill Nerode theorem. We need a separate state for $(\#a \mod \ 6 \in \{ 0..5\})$ and $(\#b \mod \ 8 \in \{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
by

18 Comments

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
7
same 48 states ..no of final states increased and .. if they asked for same symbol then we have to take lcm
18
18

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

explain this  sid1221

0
0
3
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.
4
4
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 ?
1
1
@Spandan, how mod 8 dfa can be done in 4 states?
0
0
edited by

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?

Anyone please clarify.

6
6

@Shivateja MST yes absolutely correct.

1
1
0
0
  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.

10
10
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.
0
0
No. In fact if we do that then the answer to this question should be 24, but 48 is the correct answer
2
2
yes you are correct.
0
0

@vaibhavkedia968

But for condition 2 if the operation is “or” & x is a multiple of y ,then no of states will be min (x,y).

Eg – No of a’s divisible by 3 “or” no of a’s divisible by 6, in this we will be having min (3,6) = 3 states and not lcm (3,6) = 6 states.

Please correct me if I am wrong.

2
2
3
3

@Abhrajyoti00

Thanks bro for referring the link

2
2

@Abhrajyoti00 Abhi bro, thanks man. Nice link! :)

2
2
21 votes
21 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.

4 Comments

what about OR case?? can anybody give the right solution?
1
1
OR does not make a difference in this question - just some more states become final.
14
14
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.
5
5
3 votes
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)

edited by

4 Comments

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
0
Can you please mention the source or the authenticity of this, my friend.
0
0
edited by
never apply these rule...just follow properties
0
0
–4 votes
–4 votes
Option D is correct as LCM of 6 and 8 is 24, also 48 is a multiple of 24 .
by

2 Comments

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

Related questions