edited by
18,423 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$
edited by

4 Answers

Best answer
54 votes
54 votes

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
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.
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 votes
–4 votes
Option D is correct as LCM of 6 and 8 is 24, also 48 is a multiple of 24 .
Answer:

Related questions

29 votes
29 votes
3 answers
1
Kathleen asked Sep 14, 2014
15,790 views
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least$N^2$$2^N$$2N$$N!$
36 votes
36 votes
2 answers
2
Kathleen asked Sep 14, 2014
5,265 views
Construct DFA's for the following languages:$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has ...