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

4 Comments

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.

5 Comments

I found answer as c).....can someone please explain....
0
0
if the condition would have been OR, then the min dfa will contain 14 or 15 states ?
0
0
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